Toughness and Matching Extension in $${\mathcal{P}_3}$$ -Dominated Graphs
| Autor: | Metrose Metsidik, Elkin Vumar |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | Graphs and Combinatorics. 26:425-432 |
| ISSN: | 1435-5914 0911-0119 |
| Popis: | Let G be a connected graph. For $${x,y\in V(G)}$$with d(x, y) = 2, we define $${J(x,y)= \{u \in N(x)\cap N(y)\mid N[u] \subseteq N[x] \,{\cup}\,N[y] \}}$$and $${J'(x,y)= \{u \in N(x) \cap N(y)\,{\mid}\,{\rm if}\ v \in N(u){\setminus}(N[x] \,{\cup}\, N[y])\ {\rm then}\ N[x] \,{\cup}\, N[y]\,{\cup}\,N[u]{\setminus}\{x,y\}\subseteq N[v]\}}$$. A graph G is quasi-claw-free if $${J(x,y) \not= \emptyset}$$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 $${\mathcal{P}_{3}}$$-dominated graphs defined as $${J(x,y)\,{\cup}\, J'(x,y)\not= \emptyset}$$for each $${x,y \in 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 $${\mathcal{P}_3}$$-dominated graph is 1-tough, with two exceptions: K 2,3 and K 1,1,3, and prove that every even connected $${\mathcal{P}_3}$$-dominated graph $${G\ncong K_{1,3}}$$has a perfect matching. Moreover, we show that every even (2p + 1)-connected $${\mathcal{P}_3}$$-dominated graph is p-extendable. This result follows from a stronger result concerning factor-criticality of $${\mathcal{P}_3}$$-dominated graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|