Edge number of 3-connected diameter 3 graphs

Ming Chun Tsai*, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

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 l 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.

Original languageEnglish
Pages364-367
Number of pages4
DOIs
StatePublished - May 2004
EventProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN - Hong Kong, China
Duration: 10 May 200412 May 2004

Conference

ConferenceProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
Country/TerritoryChina
CityHong Kong
Period10/05/0412/05/04

Keywords

  • Connectivity
  • Decay number
  • Diameter
  • Edge number

Cite this