zbMATH — the first resource for mathematics

On minimal graphs of diameter 2 with every edge in a 3-cycle. (English) Zbl 0603.05040
V. Chvátal and C. Thomassen [Distances in orientations of graphs, J. Comb. Theory, Ser. B 24, 61-75 (1978; Zbl 0311.05115)] proved that every bridgeless graph G of diameter 2 admits an orientation of diameter at most 6. The only difficult part of the proof is in the case that G has a minimal spanning bridgeless subgraph G’ with diameter 2 and with every edge in a 3-cycle. (Minimal here means that the diameter of G’-e is larger than 2 for all edges e.) A few years ago the author conjectured there are no graphs such as G’; if true the above proof would be greatly simplified. However, the conjecture is false and the main purpose of this article is to present an infinite class of counterexamples. He also points out that there are infinitely many planar graphs of this type of diameter k for each \(k\geq 3\).
Reviewer: R.L.Hemminger

05C99 Graph theory
05C35 Extremal problems in graph theory
Full Text: EuDML
[1] BEHZAD M., CHARTRAND G., LESNIAK-FOSTER L.: Graphs and Digraphs. Prindle, Weber and Schmidt, Boston, 1979. · Zbl 0403.05027
[2] BERMOND J. C., BOLLOBÁS B.: The diameter of graphs - a survey. Proc. 12th S. E. Conf. Graph Theory and Computing. Congressus Numerantium 32, 1981, 3-27. · Zbl 0504.05038
[3] BERMOND J. C., BOND J., PAOLI M., PEYRAT C.: Graphs and interconnection networks: diameter and vulnerability. Proc. 9th British Combinatorial Conference. London Math. Society, London, 1983, 1-30. · Zbl 0525.05018
[4] CACETTA L., HAGGKVIST R.: On diameter critical graphs. Discrete Math. 28, 1979, 223-229.
[5] CHVÁTAL V., THOMASSEN C.: Distances in orientations of graphs. J. Combin. Theory B 24, 1978, 61-75. · Zbl 0311.05115
[6] GLIVIAK F.: On certain edge-critical graphs of a given diameter. Mat. časopis 25, 1975, 249-263. · Zbl 0311.05126
[7] GLIVJAK F., KYŠ P., PLESNÍK J.: On the extension of graphs with a given diameter without superfluous edges. Mat. časopis 19, 1969, 92-101.
[8] HARARY F.: Graph Theory. Addison-Wesley, Reading, MA, 1969. · Zbl 0196.27202
[9] KRISHNAMOORTHY V., NANDAKUMAR R.: A class of counterexamples to a conjecture on diameter critical graphs. Combinatorics and Graph Theory (Proc. Second Symp. Calcutta, 1980). Lecture Notes in Math. 885, Springer, Berlin, 1981, 297-300.
[10] PLESNÍK J.: Critical graphs of given diameter. Acta Fac. Rerum Natur. Univ. Comen. Math. 30, 1975, 71-93. · Zbl 0318.05115
[11] PLESNÍK J.: Diametrically critical tournaments. Časopis pěst. mat. 100, 1975, 361-370. · Zbl 0315.05108
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.