ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in press


J. Bensmail

Julien Bensmail

Université Côte d'Azur




A $\sigma_3$ condition for arbitrarily partitionable graphs



Discussiones Mathematicae Graph Theory

Received: 2022-05-11 , Revised: 2022-08-25 , Accepted: 2022-08-26 , Available online: 2022-09-17 ,


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.


arbitrarily partitionable graph, partition into connected subgraphs, $\sigma_3$ condition, Hamiltonian graph, traceable graph


  1. D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205–216.
  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.
  4. E. Drgas-Burchardt and E. Sidorowicz, Preface, Discuss. Math. Graph Theory 35 (2015) 313–314.
  5. J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467.
  6. E. Flandrin, H. Jung and H. Li, Hamiltonism, degree sum and neighborhood intersections, Discrete Math. 90 (1991) 41–52.
  7. R.J. Gould, Recent advances on the Hamiltonian problem: Survey III, Graphs Combin. 30 (2014) 1–46.
  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.
  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.
  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.
  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.
  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.
  18. Z. Tian, Pancyclicity in Hamiltonian Graph Theory, Ph.D. Thesis (Université Paris-Saclay, France, 2021).