Physical Sciences and Mathematics Commons^™

Nonsupereulerian Graphs With Large Size, Paul A. Catlin, Zhi-Hong Chen

Zhi-Hong Chen

No abstract provided.

On The Edge Arboricity Of A Random Graph, P. A. Catlin, Zhi-Hong Chen, E. M. Palmer

Zhi-Hong Chen

No abstract provided.

On Hamiltonian Line Graphs, Zhi-Hong Chen

Zhi-Hong Chen

No abstract provided.

Supereuleriaun Graphs And The Petersen Graph, Zhi-Hong Chen

Zhi-Hong Chen

Using a contraction method, we find some best-possible sufficient condi­tions for 3-edge-connected simple graphs such that either the graphs have spanning eulerian subgraphs or the graphs are contractible to the Petersen graph.

Supereulerian Graphs And The Petersen Graph, Ii, Zhi-Hong Chen, Hong-Jian Lai

Zhi-Hong Chen

In this note, we verify two conjectures of Catlin in [J. Graph Theory 13 (1989) 465 - 483] for graphs with at most 11 vertices. These are used to prove the following theorem which improves prior results in [10] and [13]:

Let G be a 3-edge-connected simple graph with order n. If n is large and if for every edge 11.v E E(G), d(u) + d(v) 2 % - 2, then either G has a spanning eulerian subgraph or G can be contracted to the Petersen graph.

Fan-Type Conditions For Collapsible Graphs, Zhi-Hong Chen

Zhi-Hong Chen

No abstract provided.

Connectivity Of Cycle Matroids And Bicircular Matroids, Zhi-Hong Chen, Kuang Ying-Qiang, Hong-Jian Lai

Zhi-Hong Chen

A unified approach to prove former connectivity results of Tutte, Cunningham, Inukai and Weinberg, Oxley and Wagner.

Reinforcing The Number Of Disjoint Spanning Trees, Damin Liu, Hong-Jian Lai, Zhi-Hong Chen

Zhi-Hong Chen

The spanning tree packing number of a connected graph G, denoted by _T(G), is the maximum number of edge-disjoint spanning trees of G. In this paper, we determine the minimum number of edges that must be added to G so that the resulting graph has spanning tree packing number at least k, for a given value of k.

Even Subgraphs Of A Graph, Hong-Jian Lai, Zhi-Hong Chen

Zhi-Hong Chen

No abstract provided.

Spanning Eulerian Subgraphs And Catlin’S Reduced Graphs, Wei-Guo Chen, Zhi-Hong Chen

Zhi-Hong Chen

A graph G is collapsible if for every even subset R ⊆ V (G), there is a spanning connected subgraph H_R of G whose set of odd degree vertices is R. A graph is reduced if it has no nontrivial collapsible subgraphs. Catlin [4] showed that the existence of spanning Eulerian subgraphs in a graph G can be determined by the reduced graph obtained from G by contracting all the collapsible subgraphs of G. In this paper, we present a result on 3-edge-connected reduced graphs of small orders. Then, we prove that a 3-edge-connected graph G of order n …

Properties Of Catlin’S Reduced Graphs And Supereulerian Graphs, Wei-Guo Chen, Zhi-Hong Chen, Mei Lu

Zhi-Hong Chen

A graph G is called collapsible if for every even subset R ⊆ V (G), there is a spanning connected subgraph H of G such that R is the set of vertices of odd degree in H. A graph is the reduction of G if it is obtained from G by contracting all the nontrivial collapsible subgraphs. A graph is reduced if it has no nontrivial collapsible subgraphs. In this paper, we first prove a few results on the properties of reduced graphs. As an application, for 3-edge-connected graphs G of order n with d(u) + d(v) ≥ 2(n/p − …

Lai’S Conditions For Spanning And Dominating Closed Trails, Wei-Guo Chen, Zhi-Hong Chen, Mei Lu

Zhi-Hong Chen

No abstract provided.

Degree And Neighborhood Conditions For Hamiltonicity Of Claw-Free Graphs, Zhi-Hong Chen

Zhi-Hong Chen

For a graph H , let σ t ( H ) = min { Σ i = 1 t d H ( v i ) | { v 1 , v 2 , … , v t } is an independent set in H } and let U t ( H ) = min { | ⋃ i = 1 t N H ( v i ) | | { v 1 , v 2 , ⋯ , v t } is an independent set in H } . We show that for a given number ϵ and given integers …

Circumferences Of 3-Connected Claw-Free Graphs, Ii, Zhi-Hong Chen

Zhi-Hong Chen

For a graph H , the circumference of H , denoted by c ( H ) , is the length of a longest cycle in H . It is proved in Chen (2016) that if H is a 3-connected claw-free graph of order n with δ ≥ 8 , then c ( H ) ≥ min { 9 δ − 3 , n } . In Li (2006), Li conjectured that every 3-connected k -regular claw-free graph H of order n has c ( H ) ≥ min { 10 k − 4 , n } . Later, Li posed …

The Hamiltonian Index Of Graphs, Yi Hong, Jian-Liang Lin, Zhi-Sui Tao, Zhi-Hong Chen

Zhi-Hong Chen

The Hamiltonian index of a graph G is defined as h ( G ) = min { m : L m ( G ) is Hamiltonian } . In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph H ̃ ( m ) ( G ) from G and prove that if h ( G ) ≥ 2 , then h ( G ) = min{ m : H ̃ ( m ) ( G ) has a spanning Eulerian subgraph …

The Hamiltonian Index Of Graphs, Zhi-Hong Chen, Yi Hong, Jian-Liang Lin, Zhi-Sui Tao

Zhi-Hong Chen

The Hamiltonian index of a graph GG is defined as h(G)=min{m:Lm(G) is Hamiltonian}.h(G)=min{m:Lm(G) is Hamiltonian}. In this paper, using the reduction method of Catlin [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44], we constructed a graph sourceH̃^(m)(G) from GG and prove that if h(G)≥2h(G)≥2, then h(G) = min{m : H̃^(m)(G) has a spanning Eulerian subgraph}.

Spanning Eulerian Subgraphs In Claw-Free Graphs, Zhi-Hong Chen, Hong-Jian Lai, Weiqi Luo, Yehomg Shao

Zhi-Hong Chen

A graph is claw-free if it has no induced K 1,3, subgraph. A graph is essential 4-edge-connected if removing at most three edges, the resulting graph has at most one component having edges. In this note, we show that every essential 4-edge-connected claw free graph has a spanning Eulerian subgraph with maximum degree at most 4.

Spanning Trails Containing Given Edges, Weiqi Luo, Zhi-Hong Chen, Wei-Guo Chen

Zhi-Hong Chen

A graph G is Eulerian-connected if for any u and v in V ( G ) , G has a spanning ( u , v ) -trail. A graph G is edge-Eulerian-connected if for any e ′ and e ″ in E ( G ) , G has a spanning ( e ′ , e ″ ) -trail. For an integer r ⩾ 0 , a graph is called r -Eulerian-connected if for any X ⊆ E ( G ) with | X | ⩽ r , and for any u , v ∈ V ( G ) , G …

Collapsible Graphs And Reductions Of Line Graphs, Zhi-Hong Chen, Peter C.B. Lam, Wai-Chee Shiu

Zhi-Hong Chen

A graph G is collapsible if for every even subset X ⊆ V ( G ) , G has a subgraph such that G − E ( Γ ) is connected and the set of odd-degree vertices of Γ is X . A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G . In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. …

Reductions Of Graphs And Spanning Eulerian Subgraphs, Zhi-Hong Chen

Zhi-Hong Chen