Wyniki wyszukiwania

1

Hamilton cycles in almost distance-hereditary graphs

100%

Chen B., Ning B.

Open Mathematics

|

2016

|

tom 14

|

nr 1

19-28

EN

Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree sum at least n. In this paper we prove the following two theorems: (1) Every 2-connected, claw-heavy and almost distance-hereditary graph is Hamiltonian. (2) Every 3-connected, 1-heavy and almost distance-hereditary graph is Hamiltonian. The first result improves a previous theorem of Feng and Guo [J.-F. Feng and Y.-B. Guo, Hamiltonian cycle in almost distance-hereditary graphs with degree condition restricted to claws, Optimazation 57 (2008), no. 1, 135–141]. For the second result, its connectedness condition is sharp since Feng and Guo constructed a 2-connected 1-heavy graph which is almost distance-hereditary but not Hamiltonian.

2

Heavy Subgraphs, Stability and Hamiltonicity

100%

Li B., Ning B.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 3

691-710

EN

Let G be a graph. Adopting the terminology of Broersma et al. and Čada, respectively, we say that G is 2-heavy if every induced claw (K1,3) of G contains two end-vertices each one has degree at least |V (G)|/2; and G is o-heavy if every induced claw of G contains two end-vertices with degree sum at least |V (G)| in G. In this paper, we introduce a new concept, and say that G is S-c-heavy if for a given graph S and every induced subgraph G′ of G isomorphic to S and every maximal clique C of G′, every non-trivial component of G′ − C contains a vertex of degree at least |V (G)|/2 in G. Our original motivation is a theorem of Hu from 1999 that can be stated, in terms of this concept, as every 2-connected 2-heavy and N-c-heavy graph is hamiltonian, where N is the graph obtained from a triangle by adding three disjoint pendant edges. In this paper, we will characterize all connected graphs S such that every 2-connected o-heavy and S-c-heavy graph is hamiltonian. Our work results in a different proof of a stronger version of Hu’s theorem. Furthermore, our main result improves or extends several previous results.

3

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On path-quasar Ramsey numbers

100%

Li B., Ning B.

Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica

|

2014

|

tom 68

|

nr 2

EN

Let \(G_1\) and \(G_2\) be two given graphs. The Ramsey number \(R(G_1,G_2)\) is the least integer \(r\) such that for every graph \(G\) on \(r\) vertices, either \(G\) contains a \(G_1\) or \(\overline{G}\) contains a \(G_2\). Parsons gave a recursive formula to determine the values of \(R(P_n,K_{1,m})\), where \(P_n\) is a path on \(n\) vertices and \(K_{1,m}\) is a star on \(m+1\) vertices. In this note, we study the Ramsey numbers \(R(P_n,K_1\vee F_m)\), where \(F_m\) is a linear forest on \(m\) vertices. We determine the exact values of \(R(P_n,K_1\vee F_m)\) for the cases \(m\leq n\) and \(m\geq 2n\), and for the case that \(F_m\) has no odd component. Moreover, we give a lower bound and an upper bound for the case \(n+1\leq m\leq 2n-1\) and \(F_m\) has at least one odd component.

Ograniczanie wyników

1 Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica

1 Discussiones Mathematicae Graph Theory

1 Open Mathematics

3 Ning B.

2 Li B.

1 Chen B.

1 2017

1 2016

1 2014

Hamilton cycles in almost distance-hereditary graphs

Heavy Subgraphs, Stability and Hamiltonicity

On path-quasar Ramsey numbers