For two vertices and in a connected graph , the set consists of all those vertices lying on a geodesic in . For a set of vertices of , the union of all sets for is denoted by . A set is convex if . The convexity number is the maximum cardinality of a proper convex set in . A convex set is maximum if . The cardinality of a maximum convex set in a graph is the convexity number of . For a nontrivial connected graph , a connected graph is an -convex graph if contains...
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 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.
Let be a square -matrix. Then is a Hall matrix provided it has a nonzero permanent. The Hall exponent of is the smallest positive integer , if such exists, such that is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing 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).
Hallova věta a její varianty patří k základním pilířům kombinatoriky. V textu představíme některé její klasické i méně známé aplikace. Popíšeme též ranou historii věty a příbuzných tvrzení, která je spojena nejen se jménem Philipa Halla, ale i řady dalších předních matematiků první poloviny 20. století.
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...
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.
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).