DocumentCode :
3013759
Title :
Edge number of 3-connected diameter 3 graphs
Author :
Tsai, Ming-Chun ; Fu, Hung-Lin
Author_Institution :
Dept. of Bus. Adm., Chung Hua Univ., Hsinchu, Taiwan
fYear :
2004
fDate :
10-12 May 2004
Firstpage :
364
Lastpage :
367
Abstract :
Let the decay number, ζ(G) be the minimum number of components of a cotree of a connected graph G. Let Ω 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 ≥ 2p - k for each (p,q)-graph G ε Ω, and 1 is the minimum number such that ζ(H) ≤ l - 1 for each graph H ε Ω, then k=l. Furthermore, we prove that k ≤ 11 and we find a 3-connected, diameter 3 graph with q = 2p - 8. So we have that 8 ≤ k ≤ 11 and we conjecture that k = 8.
Keywords :
graph theory; multiprocessor interconnection networks; 3-connected diameter 3 graphs; connected graph; connectivity; cotree; decay number; edge number; Costs; Councils; Graph theory; Mathematics; Multiprocessor interconnection networks; Network topology; Parallel architectures; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on
ISSN :
1087-4089
Print_ISBN :
0-7695-2135-5
Type :
conf
DOI :
10.1109/ISPAN.2004.1300506
Filename :
1300506
Link To Document :
بازگشت