Geodesic
Traceability in $\{K_{1,4},K_{1,4}+e\}$-free graphs
Czechoslovak Mathematical Journal, Tome 69 (2019) no. 2, pp. 431-442
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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}$.
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}$.
DOI : 10.21136/CMJ.2019.0365-17
Classification : 05C07, 05C38, 05C45
Keywords: $\{K_{1, 4}, K_{1, 4}+e\}$-free graph; neighborhood union; traceable 
@article{10_21136_CMJ_2019_0365_17,
     author = {Zheng, Wei and Wang, Ligong},
     title = {Traceability in $\{K_{1,4},K_{1,4}+e\}$-free graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {431--442},
     year = {2019},
     volume = {69},
     number = {2},
     doi = {10.21136/CMJ.2019.0365-17},
     mrnumber = {3959956},
     zbl = {07088796},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0365-17/}
}
TY  - JOUR
AU  - Zheng, Wei
AU  - Wang, Ligong
TI  - Traceability in $\{K_{1,4},K_{1,4}+e\}$-free graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2019
SP  - 431
EP  - 442
VL  - 69
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0365-17/
DO  - 10.21136/CMJ.2019.0365-17
LA  - en
ID  - 10_21136_CMJ_2019_0365_17
ER  - 
%0 Journal Article
%A Zheng, Wei
%A Wang, Ligong
%T Traceability in $\{K_{1,4},K_{1,4}+e\}$-free graphs
%J Czechoslovak Mathematical Journal
%D 2019
%P 431-442
%V 69
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0365-17/
%R 10.21136/CMJ.2019.0365-17
%G en
%F 10_21136_CMJ_2019_0365_17
Zheng, Wei; Wang, Ligong. Traceability in $\{K_{1,4},K_{1,4}+e\}$-free graphs. Czechoslovak Mathematical Journal, Tome 69 (2019) no. 2, pp. 431-442. doi: 10.21136/CMJ.2019.0365-17

[1] Bauer, D., Fan, G., Veldman, H. J.: Hamiltonian properties of graphs with large neighborhood unions. Discrete Math. 96 (1991), 33-49. | DOI | MR | JFM

[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. American Elsevier Publishing, New York (1976). | DOI | MR | JFM

[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. | DOI | MR | JFM

[4] Li, R.: Hamiltonicity of 2-connected $\{K_{1,4},K_{1,4}+e\}$-free graphs. Discrete Math. 287 (2004), 69-76. | DOI | MR | JFM

[5] Li, R., Schelp, R. H.: Hamiltonicity of {$\{K_{1,4},K_{1,4}+e\}$}-free graphs. Discrete Math. 245 (2002), 195-202. | DOI | MR | JFM

[6] Lin, H., Wang, J.: Hamilton paths in {$\{K_{1,4},K_{1,4}+e\}$}-free graphs. Discrete Math. 308 (2008), 4280-4285. | DOI | MR | JFM

Cité par Sources :