Toughness and Matching Extension in P₃{mathcal{P}_3}-Dominated Graphs

摘要

Let G be a connected graph. For with d(x, y) = 2, we define and . A graph G is quasi-claw-free if 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 -dominated graphs defined as for each 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 -dominated graph is 1-tough, with two exceptions: K _2,3 and K _1,1,3, and prove that every even connected -dominated graph has a perfect matching. Moreover, we show that every even (2p + 1)-connected -dominated graph is p-extendable. This result follows from a stronger result concerning factor-criticality of -dominated graphs.