MINIMAL REGULAR GRAPH CONTAINING A GIVEN GRAPH

被引：1
|
作者：
SHASTRI, A [1 ]
机构：
[1] MIT,DEPT MATH,CAMBRIDGE,MA 02139
来源：
APPLIED MATHEMATICS LETTERS | 1992年 / 5卷 / 01期
关键词：
D O I：
10.1016/0893-9659(92)90124-R
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
It is shown that every graph on n vertices can be realized as an induced subgraph of a regular graph on at most 2n - 2 vertices and this is the best realization possible. The proof uses an extension of a theorem of Erdos and Kelley, and some related results are also deduced.
引用
收藏
页码：3 / 5
页数：3
相关论文
共 50 条
  • [1] MINIMAL REGULAR GRAPH CONTAINING A GIVEN GRAPH
    ERDOS, P
    KELLY, P
    AMERICAN MATHEMATICAL MONTHLY, 1963, 70 (10): : 1074 - &
  • [2] MINIMUM BLOCK CONTAINING A GIVEN GRAPH
    PLESNIK, J
    ARCHIV DER MATHEMATIK, 1976, 27 (06) : 668 - 672
  • [3] ON GRAPHS CONTAINING A GIVEN GRAPH AS CENTER
    BUCKLEY, F
    MILLER, Z
    SLATER, PJ
    JOURNAL OF GRAPH THEORY, 1981, 5 (04) : 427 - 434
  • [4] MINIMAL GRAPH WITH A GIVEN NUMBER OF SPANNING TREES
    SEDLACEK, J
    CANADIAN MATHEMATICAL BULLETIN, 1970, 13 (04): : 515 - &
  • [5] ON LEAST EIGENVALUE OF A GRAPH OF LARGE MINIMUM VALENCE CONTAINING A GIVEN GRAPH
    HOFFMAN, AJ
    SIAM REVIEW, 1968, 10 (02) : 268 - &
  • [6] MAXIMIZING THE ORDER OF A REGULAR GRAPH OF GIVEN VALENCY AND SECOND EIGENVALUE
    Cioaba, Sebastian M.
    Koolen, Jack H.
    Nozaki, Hiroshi
    Vermette, Jason R.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (03) : 1509 - 1525
  • [7] The 3-Xline Graph of a Given Graph
    Johns, Garry
    Wang, Bianka
    Zayed, Mohra
    Journal of Combinatorial Mathematics and Combinatorial Computing, 2020, 114 : 181 - 191
  • [8] Algebraic connectivity of the line graph, the middle graph and the total graph of a regular graph
    Nihei, M
    ARS COMBINATORIA, 2003, 69 : 215 - 221
  • [9] Numerous graph energies of regular subdivision graph and complete graph
    Kousar, Imrana
    Nazeer, Saima
    Mahboob, Abid
    Shahid, Sana
    Lv, Yu-Pei
    AIMS MATHEMATICS, 2021, 6 (08): : 8466 - 8476
  • [10] REGULAR SUBGRAPHS OF A REGULAR GRAPH
    KANO, M
    ANNALS OF THE NEW YORK ACADEMY OF SCIENCES, 1989, 576 : 281 - 284
12345