Toughness and Matching Extension in P3-Dominated Graphs
Metrose Metsidik, Elkin Vumar · 2010
Let G be a connected graph. For x, y ∈ V (G) with d(x, y) = 2, we define J (x, y) ={ u ∈ N (x) ∩ N (y) | N (u )⊆ N (x )∪ N (y)} and J � (x, y) ={ u ∈ N (x)∩ N (y) | if v ∈ N (u)\(N (x )∪ N (y)) then N (x )∪ N (y )∪ N (u)\{x, y }⊆ N (v)}. A graph G is quasi-claw-free if J (x, y) � =∅ for each pair (x, y) of vertices at distance 2 in G. Broersma and Vumar (in Math Meth Oper Res. doi:10.1007/s00186-008-0260-7) introduced P3-dominated graphs defined as J (x, y) ∪ J � (x, y) � for each x, y ∈ V (G) with d(x, y) = 2. This class properly contains that of quasi-claw-free graphs, and hence that of claw-free graphs. In this note, we prove that a 2-connected P3-dom- inated graph is 1-tough, with two exceptions: K2,3 and K1,1,3, and prove that every even connected P3-dominated graph G K1,3 has a perfect matching. Moreover, we show that every even (2 p + 1)-connected P3-dominated graph is p-extendable. This result follows from a stronger result concerning factor-criticality of P3-dominated graphs.