Article in volume
Authors:
Title:
A $\sigma_3$ condition for arbitrarily partitionable graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 755-776
Received: 2022-05-11 , Revised: 2022-08-25 , Accepted: 2022-08-26 , Available online: 2022-09-17 , https://doi.org/10.7151/dmgt.2471
Abstract:
A graph $G$ of order $n$ is arbitrarily partitionable (AP for short) if, for
every partition $(\lambda_1,\dots,\lambda_p)$ of $n$, there is a partition
$(V_1,\dots,V_p)$ of $V(G)$ such that $G[V_i]$ is a connected graph of order
$\lambda_i$ for every $i \in \{1,\dots,p\}$. Several aspects of AP graphs have
been investigated to date, including their connection to Hamiltonian graphs and
traceable graphs. Every traceable graph (and, thus, Hamiltonian graph) is indeed
known to be AP, and a line of research on AP graphs is thus about weakening, to
APness, known sufficient conditions for graphs to be Hamiltonian or traceable.
In this work, we provide a sufficient condition for APness involving the
parameter $\overline{\sigma_3}$, where, for a given graph $G$, the parameter
$\overline{\sigma_3}(G)$ is defined as the minimum value of
$d(u)+d(v)+d(w)-|N(u) \cap N(v) \cap N(w)|$ for a set $\{u,v,w\}$ of three
pairwise independent vertices $u$, $v$, and $w$ of $G$. Flandrin, Jung, and Li
proved that any graph $G$ of order $n$ is Hamitonian provided $G$ is
$2$-connected and $\overline{\sigma_3}(G) \geq n$, and traceable provided
$\overline{\sigma_3}(G) \geq n-1$. Unfortunately, we exhibit examples showing
that having $\overline{\sigma_3}(G) \geq n-2$ is not a guarantee for $G$ to
be AP. However, we prove that $G$ is AP provided $G$ is $2$-connected,
$\overline{\sigma_3}(G) \geq n-2$, and $G$ has a perfect matching or
quasi-perfect matching.
Keywords:
arbitrarily partitionable graph, partition into connected subgraphs, $\sigma_3$ condition, Hamiltonian graph, traceable graph
References:
- D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205–216.
https://doi.org/10.1016/S0166-218X(00)00322-X - J. Bensmail, Partitions and Decompositions of Graphs, Ph.D. Thesis (Université de Bordeaux, France, 2014).
- J. Bensmail and B. Li, More aspects of arbitrarily partitionable graphs, Discuss. Math. Graph Theory 42 (2022) 1237–1261.
https://doi.org/10.7151/dmgt.2343 - E. Drgas-Burchardt and E. Sidorowicz, Preface, Discuss. Math. Graph Theory 35 (2015) 313–314.
https://doi.org/10.7151/dmgt.1809 - J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467.
https://doi.org/10.4153/CJM-1965-045-4 - E. Flandrin, H. Jung and H. Li, Hamiltonism, degree sum and neighborhood intersections, Discrete Math. 90 (1991) 41–52.
https://doi.org/10.1016/0012-365X(91)90094-I - R.J. Gould, Recent advances on the Hamiltonian problem: Survey III, Graphs Combin. 30 (2014) 1–46.
https://doi.org/10.1007/s00373-013-1377-x - E. Győri, On division of graphs to connected subgraphs, in: Proc. 5th Hungarian Combinational Colloquium (1978) 485–494.
- M. Horňák, A. Marczyk, I. Schiermeyer and M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012) 807–821.
https://doi.org/10.1007/s00373-011-1077-3 - M. Horňák and M. Woźniak, Arbitrarily vertex decomposable trees are of degree at most $6$, Opuscula Math. 23 (2003) 49–62.
- R. Kalinowski, M. Pilśniak, I. Schiermeyer and M. Woźniak, Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5–22.
https://doi.org/10.7151/dmgt.1833 - L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 241–251.
- A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118.
- A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009) 3588–3594.
https://doi.org/10.1016/j.disc.2007.12.066 - B. Momege, Sufficient conditions for a connected graph to have a Hamiltonian path, in: Proceedings of the 2017 International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2017), B. Steffen, C. Baier, M. van den Brand, J. Eder, M. Hinchey and T. Mengaria (Ed(s)), (Theory and Practise of Computer Science, LNCS 10139 2017) 205–216.
https://doi.org/10.1007/978-3-319-51963-0_16 - O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
- R. Ravaux, Decomposing trees with large diameter, Theoret. Comput. Sci. 411 (2010) 3068–3072.
https://doi.org/10.1016/j.tcs.2010.04.032 - Z. Tian, Pancyclicity in Hamiltonian Graph Theory, Ph.D. Thesis (Université Paris-Saclay, France, 2021).
Close