Edge number of 3-connected diameter 3 graphs

被引:0
作者
Tsai, MC [1 ]
Fu, HL [1 ]
机构
[1] Chung Hua u niv, Dept Business Adm, Hsinchu 300, Taiwan
来源
I-SPAN 2004: 7TH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND NETWORKS, PROCEEDINGS | 2004年
关键词
connectivity; diameter; decay number; edge number;
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Let the decay number, sigma(G) be the minimum number of components of a cotree of a connected graph G. Let Omega be the collection of all 3-connected diameter 3 graphs. In this paper, we prove that if k is the minimum number such that q greater than or equal to 2p-k for each (p, q) - graph G is an element of Omega, and l is the minimum number such that sigma(H) less than or equal to l-1 for each graph H is an element of Omega, then k = l. Furthermore, we prove that k less than or equal to 11 and we find a 3-connected, diameter 3 graph with q = 2p-8. So we have that 8 less than or equal to k less than or equal to 11 and we conjecture that k = 8.
引用
收藏
页码:364 / 367
页数:4
相关论文
共 4 条
  • [1] The decay number and the maximum genus of diameter 2 graphs
    Fu, HL
    Tsai, MC
    Xuong, NH
    [J]. DISCRETE MATHEMATICS, 2001, 226 (1-3) : 191 - 197
  • [2] MURTY USR, 1969, ACTA MATH ACAD SCI H, V19, P69
  • [3] Nebesky L., 1995, MATH SOLVACA, V45, P349
  • [4] Skoviera M., 1992, MATH SLOVACA, V42, P391