Displaying similar documents to “A graph and its complement with specified properties. I: Connectivity.”

Structural Properties of Recursively Partitionable Graphs with Connectivity 2

Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika Pilśniak (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition...

The Existence Of P≥3-Factor Covered Graphs

Sizhong Zhou, Jiancheng Wu, Tao Zhang (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A spanning subgraph F of a graph G is called a P≥3-factor of G if every component of F is a path of order at least 3. A graph G is called a P≥3-factor covered graph if G has a P≥3-factor including e for any e ∈ E(G). In this paper, we obtain three sufficient conditions for graphs to be P≥3-factor covered graphs. Furthermore, it is shown that the results are sharp.