Hamilton Circuits and Essential Girth of Claw Free Graphs

2016 
Let $$G$$G be a $$K_{1,3}$$K1,3-free graph. A circuit of $$G$$G is essential if it contains a non-locally connected vertex $$v$$v and passes through both components of $$N(v)$$N(v). The essential girth of $$G$$G, denoted by $$g_e(G)$$ge(G), is the length of a shortest essential circuit. It can be seen easily that, by Ryjaă?ek closure operation, the essential girth of $$G$$G is closely related to the girth of $$H$$H where $$H$$H is the Ryjaă?ek closure of $$G$$G and is a line graph. A generalized net, denoted by $$N_{i_1,i_2,i_3}$$Ni1,i2,i3, is a graph obtained from a triangle $$C_3$$C3 and three disjoint paths $$P_{i_\mu +1}$$Piμ+1 ($$\mu =1,2,3$$μ=1,2,3), by identifying each vertex $$v_\mu $$vμ of $$C_3=v_1v_2v_3v_1$$C3=v1v2v3v1 with an end vertex of the path $$P_{i_\mu +1}$$Piμ+1, for every $$\mu = 1,2,3$$μ=1,2,3. In this paper, we prove that every $$2$$2-connected $$\{ K_{1,3}, N_{1,1,g_e(G)-4}\}$${K1,3,N1,1,ge(G)-4}-free (and $$\{ K_{1,3}, N_{1,0,g_e(G)-3}\}$${K1,3,N1,0,ge(G)-3}-free) graph $$G$$G contains a Hamilton circuit. With the additional parameter $$g_e$$ge, these results extend some earlier theorems about Hamilton circuits in $$\{ K_{1,3}, N_{a,b,c}\}$${K1,3,Na,b,c}-free graphs (for some small integers $$a, b$$a,b and $$c$$c).
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    15
    References
    0
    Citations
    NaN
    KQI
    []