zbMATH — the first resource for mathematics

On 4-connected, planar 4-almost pancyclic graphs. (English) Zbl 0681.05047
A k-almost pancylic graph is one in which there are cycles of all lengths except k. In this paper, constructive methods are used to demonstrate the existence of 4-connected planar 4-almost pancyclic graphs on v vertices for \(v=30,36,39,42,44,45,46\) and all \(v\geq 48\). In addition, it is shown that these are the only values of v for which such graphs exist.
Reviewer: R.E.L.Aldred
05C40 Connectivity
05C38 Paths and cycles
Full Text: EuDML
[1] BARI R. A.: Regular Major Maps of at Most 19 Regions and their Q-Chromials. J. Comb. Theory Ser. B 12, 1972, 132-142. · Zbl 0211.56603
[2] BONDY J. A.: Pancyclic Graph. J. Comb. Theory Ser. B 11, 1971, 80-84. · Zbl 0183.52301
[3] CHOUDUM S. A.: Some 4-valent, 3-connected, planar, almost pancyclic graphs. Discrete Math. 18, 1977, 125-129. · Zbl 0357.05040
[4] MALKEVITCH J.: On the lengths of cycles in planar graphs. Recent Trends in Graph Theory (Proc. Conf., New York 1970), pp. 191 - 195. Lecture Notes in Mathematics, Vol. 186, Springer, Berlin 1971.
[5] ORE O.: The four color problem. Academia Press 1967. · Zbl 0149.21101
[6] TUTTE W. T.: A theorem on planar graphs. Trans. Amer. Math. Soc. 82, 1956, 99 - 116. · Zbl 0070.18403
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.