Article in volume
Authors:
Jan Ekstein
DEPARTMENT OF MATHEMATICS
University of West Bohemia
Univerzitní 2732/8
301 00 Pilsen
email: ekstein@kma.zcu.cz
Title:
Hamiltonian properties in generalized lexicographic products
PDFSource:
Discussiones Mathematicae Graph Theory 45(1) (2025) 219-237
Received: 2023-05-15 , Revised: 2023-10-25 , Accepted: 2023-10-25 , Available online: 2023-11-14 , https://doi.org/10.7151/dmgt.2527
Abstract:
The lexicographic product $G[H]$ of two graphs $G$ and $H$ is obtained from $G$
by replacing each vertex with a copy of $H$ and adding all edges between any
pair of copies corresponding to adjacent vertices of $G$. We consider also the
generalized lexicographic product such that we replace each vertex of $G$ with
arbitrary graph on the same number of vertices. We present sufficient and
necessary conditions for traceability, hamiltonicity and hamiltonian
connectivity of $G[H]$ if $G$ is a path and hence we improved and extended
results in [M. Kriesell, A note on Hamiltonian cycles in lexicographical
products, J. Autom. Lang. Comb. 2 (1997) 135–138].
Keywords:
lexicographic products, hamiltonian cycles and paths
References:
- Z. Baranyai and Gy.R. Szász, Hamiltonian decomposition of lexicographic product, J. Combin. Theory Ser. B 31 (1981) 253–261.
https://doi.org/10.1016/0095-8956(81)90028-9 - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer, New York, 2008).
- R. Gu and H. Hou, End-regular and End-orthodox generalized lexicographic products of bipartite graphs, Open Math. 14 (2016) 229–236.
https://doi.org/10.1515/math-2016-0021 - S.A. Choudum and T. Karthick, Maximal cliques in $\{P_2\cup P_3,C_4\}$-free graphs, Discrete Math. 310 (2010) 3398–3403.
https://doi.org/10.1016/j.disc.2010.08.005 - T. Kaiser and M. Kriesell, On the pancyclicity of lexicographic products, Graphs Combin. 22 (2006) 51–58.
https://doi.org/10.1007/s00373-005-0639-7 - M. Kriesell, A note on Hamiltonian cycles in lexicographical products, J. Autom. Lang. Comb. 2 (1997) 135–138.
- L.L. Ng, Hamiltonian decomposition of lexicographic products of digraphs, J. Combin. Theory Ser. B 73 (1998) 119–129.
https://doi.org/10.1006/jctb.1998.1816 - V. Samodivkin, Domination related parameters in the generalized lexicographic product of graphs, Discrete Appl. Math. 300 (2021) 77–84.
https://doi.org/10.1016/j.dam.2021.03.015 - H.-M. Teichert, Hamiltonian properties of the lexicographic product of undirected graphs, Elektronische Informationsverarbeitung Kybernetik 19 (1983) 67–77.
Close