Name
Title | ||
|---|---|---|
Characterizing the Difference Between Graph Classes Defined by Forbidden Pairs Including the Claw. |
Abstract | ||
|---|---|---|
For two graphs A and B, a graph G is called $$\{A,B\}$$-free if G contains neither A nor B as an induced subgraph. Let $$P_{n}$$ denote the path of order n. For nonnegative integers k, $$\ell $$ and m, let $$N_{k,\ell ,m}$$ be the graph obtained from $$K_{3}$$ and three vertex-disjoint paths $$P_{k+1}$$, $$P_{\ell +1}$$, $$P_{m+1}$$ by identifying each of the vertices of $$K_{3}$$ with one endvertex of one of the paths. Let $$Z_{k}=N_{k,0,0}$$ and $$B_{k,\ell }=N_{k,\ell ,0}$$. Bedrossian characterized all pairs $$\{A,B\}$$ of connected graphs such that every 2-connected $$\{A,B\}$$-free graph is Hamiltonian. All pairs appearing in the characterization involve the claw ($$K_{1,3}$$) and one of $$N_{1,1,1}$$, $$P_{6}$$ and $$B_{1,2}$$. In this paper, we characterize connected graphs that are (i) $$\{K_{1,3},Z_{2}\}$$-free but not $$B_{1,1}$$-free, (ii) $$\{K_{1,3},B_{1,1}\}$$-free but not $$P_{5}$$-free, or (iii) $$\{K_{1,3},B_{1,2}\}$$-free but not $$P_{6}$$-free. The third result is closely related to Bedrossian’s characterization. Furthermore, we apply our characterizations to some forbidden pair problems. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00373-019-02108-0 | Graphs and Combinatorics |
Keywords | Field | DocType |
Forbidden subgraph, Hamiltonian cycle, Halin graph | Integer,Graph,Combinatorics,Vertex (geometry),Hamiltonian path,Induced subgraph,Halin graph,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 6 | 0911-0119 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guantao Chen | 1 | 107 | 25.00 |
| Michitaka Furuya | 2 | 39 | 18.35 |
| Songling Shan | 3 | 20 | 9.16 |
| Shoichi Tsuchiya | 4 | 9 | 4.44 |
| Ping Yang | 5 | 0 | 0.68 |