| Title:
|
Traceability in $\{K_{1,4},K_{1,4}+e\}$-free graphs (English) |
| Author:
|
Zheng, Wei |
| Author:
|
Wang, Ligong |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
69 |
| Issue:
|
2 |
| Year:
|
2019 |
| Pages:
|
431-442 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
A graph $G$ is called $\{H_1,H_2, \dots ,H_k\}$-free if $G$ contains no induced subgraph isomorphic to any graph $H_i$, $1\leq i\leq k$. We define $$\sigma _k= \min \biggl \{ \sum _{i=1}^k d(v_i) \colon \{v_1, \dots ,v_k\}\ \text {is an independent set of vertices in}\ G \biggr \}.$$ In this paper, we prove that (1) if $G$ is a connected $\{K_{1,4},K_{1,4}+e\}$-free graph of order $n$ and $\sigma _3(G)\geq n-1$, then $G$ is traceable, (2) if $G$ is a 2-connected $\{K_{1,4},K_{1,4}+e\}$-free graph of order $n$ and $|N(x_1)\cup N(x_2)|+|N(y_1)\cup N(y_2)|\geq n-1$ for any two distinct pairs of non-adjacent vertices $\{x_1,x_2\}$, $\{y_1,y_2\}$ of $G$, then $G$ is traceable, i.e., $G$ has a Hamilton path, where $K_{1,4}+e$ is a graph obtained by joining a pair of non-adjacent vertices in a $K_{1,4}$. (English) |
| Keyword:
|
$\{K_{1,4},K_{1,4}+e\}$-free graph |
| Keyword:
|
neighborhood union |
| Keyword:
|
traceable |
| MSC:
|
05C07 |
| MSC:
|
05C38 |
| MSC:
|
05C45 |
| idZBL:
|
Zbl 07088796 |
| idMR:
|
MR3959956 |
| DOI:
|
10.21136/CMJ.2019.0365-17 |
| . |
| Date available:
|
2019-05-24T08:59:01Z |
| Last updated:
|
2021-07-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147736 |
| . |
| Reference:
|
[1] Bauer, D., Fan, G., Veldman, H. J.: Hamiltonian properties of graphs with large neighborhood unions.Discrete Math. 96 (1991), 33-49. Zbl 0741.05039, MR 1139438, 10.1016/0012-365X(91)90468-H |
| Reference:
|
[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.American Elsevier Publishing, New York (1976). Zbl 1226.05083, MR 0411988, 10.1007/978-1-349-03521-2 |
| Reference:
|
[3] Duan, F., Wang, G. P.: Note on the longest paths in {$\{K_{1,4},K_{1,4}+e\}$}-free graphs.Acta Math. Sin., Engl. Ser. 28 (2012), 2501-2506. Zbl 1259.05091, MR 2995196, 10.1007/s10114-012-0459-7 |
| Reference:
|
[4] Li, R.: Hamiltonicity of 2-connected $\{K_{1,4},K_{1,4}+e\}$-free graphs.Discrete Math. 287 (2004), 69-76. Zbl 1052.05505, MR 2094057, 10.1016/j.disc.2004.05.014 |
| Reference:
|
[5] Li, R., Schelp, R. H.: Hamiltonicity of {$\{K_{1,4},K_{1,4}+e\}$}-free graphs.Discrete Math. 245 (2002), 195-202. Zbl 0995.05086, MR 1887938, 10.1016/S0012-365X(01)00141-8 |
| Reference:
|
[6] Lin, H., Wang, J.: Hamilton paths in {$\{K_{1,4},K_{1,4}+e\}$}-free graphs.Discrete Math. 308 (2008), 4280-4285. Zbl 1235.05075, MR 2427760, 10.1016/j.disc.2007.08.051 |
| . |
