All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 104 Next

Displaying 2061 – 2080 of 5365

Showing per page

Hajós' theorem for list colorings of hypergraphs

Claude Benzaken, Sylvain Gravier, Riste Skrekovski (2003)

Discussiones Mathematicae Graph Theory

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph K k + 1 by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós’ theorem to list-colorings of hypergraphs.

Hall exponents of matrices, tournaments and their line digraphs

Richard A. Brualdi, Kathleen P. Kiernan (2011)

Czechoslovak Mathematical Journal

Let A be a square ( 0 , 1 ) -matrix. Then A is a Hall matrix provided it has a nonzero permanent. The Hall exponent of A is the smallest positive integer k , if such exists, such that A k is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing A as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).

Hamilton cycles in almost distance-hereditary graphs

Bing Chen, Bo Ning (2016)

Open Mathematics

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...

Hamilton cycles in split graphs with large minimum degree

Ngo Dac Tan, Le Xuan Hung (2004)

Discussiones Mathematicae Graph Theory

A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.

Hamilton decompositions of line graphs of some bipartite graphs

David A. Pike (2005)

Discussiones Mathematicae Graph Theory

Some bipartite Hamilton decomposable graphs that are regular of degree δ ≡ 2 (mod 4) are shown to have Hamilton decomposable line graphs. One consequence is that every bipartite Hamilton decomposable graph G with connectivity κ(G) = 2 has a Hamilton decomposable line graph L(G).

Hamiltonian colorings of graphs with long cycles

Ladislav Nebeský (2003)

Mathematica Bohemica

By a hamiltonian coloring of a connected graph G of order n ≥ 1 we mean a mapping c of V ( G ) into the set of all positive integers such that | c ( x ) - c ( y ) | ≥ n - 1 - D G ( x , y ) (where D G ( x , y ) denotes the length of a longest x - y path in G ) for all distinct x , y ∈ G . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order n ≥ 5 with circumference n - 2 .

Hamiltonian connectedness and a matching in powers of connected graphs

Elena Wisztová (1995)

Mathematica Bohemica

In this paper the following results are proved: 1. Let P n be a path with n vertices, where n ≥ 5 and n ≠ 7 , 8 . Let M be a matching in P n . Then ( P n ) 4 - M is hamiltonian-connected. 2. Let G be a connected graph of order p ≥ 5 , and let M be a matching in G . Then G 5 - M is hamiltonian-connected.

Currently displaying 2061 – 2080 of 5365