zbMATH — the first resource for mathematics

Fan-type theorem for path-connectivity. (English) Zbl 1002.05041
Let \(\mu(G)\) be \(\min\{\max\{d_G(u), d_G(v)\}\mid\text{distance}(u,v)= 2\}\) for a connected noncomplete graph \(G\). The authors prove that for each 3-connected noncomplete graph \(G\) each pair of distinct vertices is joined by a path of length at least \(\min\{|V(G)|- 1, 2\mu(G)- 2\}\). This proves also a conjecture of H. Enomoto, K. Hirohata and K. Ota [J. Graph Theory 24, 275-279 (1997; Zbl 0868.05033)].
Reviewer: M.Hager (Leonberg)

05C40 Connectivity
Full Text: DOI
[1] Benhocine, J Combin Theory B 42 pp 167– (1987)
[2] Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.
[3] Dirac, Proc London Math Soc 2 pp 69– (1952)
[4] Dirac, Ann Discrete Math 3 pp 75– (1978)
[5] Enomoto, J Graph Theory 8 pp 287– (1984)
[6] Enomoto, J Graph Theory 24 pp 275– (1997)
[7] Fan, J Combin Theory Ser B 37 pp 221– (1984)
[8] Tian, J Syst Sci Math Sci 6 pp 258– (1986)
[9] Wei, Ann N Y Acad Sci 576 pp 623– (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.