DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

J. Bensmail

Julien Bensmail

Université Côte d'Azur

email: julien.bensmail.phd@gmail.com

0000-0002-9292-394X

Title:

A $\sigma_3$ condition for arbitrarily partitionable graphs

PDF

Source:

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:

  1. 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
  2. J. Bensmail, Partitions and Decompositions of Graphs, Ph.D. Thesis (Université de Bordeaux, France, 2014).
  3. 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
  4. E. Drgas-Burchardt and E. Sidorowicz, Preface, Discuss. Math. Graph Theory 35 (2015) 313–314.
    https://doi.org/10.7151/dmgt.1809
  5. J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467.
    https://doi.org/10.4153/CJM-1965-045-4
  6. 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
  7. 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
  8. E. Győri, On division of graphs to connected subgraphs, in: Proc. 5th Hungarian Combinational Colloquium (1978) 485–494.
  9. 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
  10. M. Horňák and M. Woźniak, Arbitrarily vertex decomposable trees are of degree at most $6$, Opuscula Math. 23 (2003) 49–62.
  11. 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
  12. L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 241–251.
  13. A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006) 109–118.
  14. 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
  15. 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
  16. O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
  17. R. Ravaux, Decomposing trees with large diameter, Theoret. Comput. Sci. 411 (2010) 3068–3072.
    https://doi.org/10.1016/j.tcs.2010.04.032
  18. Z. Tian, Pancyclicity in Hamiltonian Graph Theory, Ph.D. Thesis (Université Paris-Saclay, France, 2021).

Close