Decompositions and packings in truncated triangulations

Michael Muzheve

Abstract


We study decompositions and packings in truncated triangulations GT△ obtained from simple connected plane graphs G with minimum degree two. We show GT△ is a 3-connected cubic planar graph with at least 2|E(G)|² - 2|E(G)| + 1 perfect matchings, a Λ-factor, and can be decomposed into a union of C₆'s and K₂'s if G is bipartite. Additionally, we show that GT△ is hamiltonian if G is bipartite with a dominating path P satisfying, for any e = xy ∉ E(P) exactly one of x and y is in V(P). We also prove a result giving necessary and sufficient conditions for the hamiltonicity of GT△. Additional results include showing that a truncated triangulation of a cubic plane bipartite graph G has a hamiltonian cycle that separates specific faces of GT△ if and only if the triangulation G△ has an A-trail.

Keywords


truncation; triangulation of the plane; cubic; perfect matching; hamiltonian; A-trail; dominating path

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.15

References

S. Arumugam, I. S. Hamid, and V. M. Abraham, "Decomposition of Graphs into Paths and Cycles," Journal of Discrete Mathematics, 2013.

M. V. Diudea and V. R. Rosenfeld, "The truncation of a cage graph," Journal of Mathematical Chemistry, vol. 55, pp. 1014–1020, 2017.

H. Fleischner, "On spanning subgraphs of a connected bridgeless graph and their application to graphs," Journal of Combinatorial Theory Series B, vol. 16, pp. 17–28, 1974.

H. Fleischner, A. M. Hobbs, and M. T. Muzheve, "Hamiltonicity in vertex envelopes of plane cubic graphs," Discrete Mathematics, vol. 309, no. 14, pp. 4793–4809, 2009.

D. W. Barnette, Conjecture attributed by B. Grünbaum in Unsolved Problem 5, p. 343, in Proc. of the Third Waterloo Conf. on Combinatorics (May 1968), in W. T. Tutte (Ed.), Recent Progress in Combinatorics, Academic Press, New York, NY, 1969.

P. W. Fowler, J. E. Cremona, and J. I. Steer, "Systematics of bonding in non-icosahedral carbon clusters," Theoretica Chimica Acta, vol. 73, pp. 1–26, 1988.

H. Harary and C. St. J. A. Nash-Williams, "On Eulerian and Hamiltonian graphs and line graphs," Canadian Mathematical Bulletin, vol. 8, no. 6, pp. 701–709, 1965.

A. K. Kelmans, "Packing 3-vertex paths in cubic 3-connected graphs," arXiv: Combinatorics, 2008.

L. Lovász, "On Covering of graphs," Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, pp. 231–236, 1968.

M. T. Muzheve, "A Sufficient Condition for the Hamiltonicity of Vertex Envelopes of Plane Graphs," Model Assisted Statistics and Applications, vol. 19, no. 4, pp. 325–331, 2024.

S. Pirzada, H. A. Ganie, and M. Siddique, "On some covering graphs of a graph," Electronic Journal of Graph Theory and Applications, vol. 4, no. 2, pp. 132–147, 2016.

X. Wang, F.-G. Yin, and J.-X. Zhou, "On generalized truncations of complete graphs," Ars Mathematica Contemporanea, vol. 19, no. 2, pp. 325–335, 2020.

N. Viswanathan and D. West, "Hamiltonian Cycles and Tight Cutsets," Graphs and Combinatorics, vol. 41, no. 1, 2024.

D. West, Introduction to Graph Theory, Prentice Hall, 2001.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats