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 6

Displaying 101 – 109 of 109

Showing per page

Onq-Power Cycles in Cubic Graphs

Julien Bensmail (2017)

Discussiones Mathematicae Graph Theory

In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8 only.

Order of the smallest counterexample to Gallai's conjecture

Fuyuan Chen (2018)

Czechoslovak Mathematical Journal

In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Zamfirescu conjectured that the smallest counterexample to Gallai’s conjecture is a graph on 12 vertices. We prove that Gallai’s conjecture is true for every connected graph G with α ' ( G ) ≤ 5 , which implies that Zamfirescu’s conjecture is true.

Ordered and linked chordal graphs

Thomas Böhme, Tobias Gerlach, Michael Stiebitz (2008)

Discussiones Mathematicae Graph Theory

A graph G is called k-ordered if for every sequence of k distinct vertices there is a cycle traversing these vertices in the given order. In the present paper we consider two novel generalizations of this concept, k-vertex-edge-ordered and strongly k-vertex-edge-ordered. We prove the following results for a chordal graph G: (a) G is (2k-3)-connected if and only if it is k-vertex-edge-ordered (k ≥ 3). (b) G is (2k-1)-connected if and only if it is strongly k-vertex-edge-ordered...

Orientation distance graphs revisited

Wayne Goddard, Kiran Kanakadandi (2007)

Discussiones Mathematicae Graph Theory

The orientation distance graph 𝓓ₒ(G) of a graph G is defined as the graph whose vertex set is the pair-wise non-isomorphic orientations of G, and two orientations are adjacent iff the reversal of one edge in one orientation produces the other. Orientation distance graphs was introduced by Chartrand et al. in 2001. We provide new results about orientation distance graphs and simpler proofs to existing results, especially with regards to the bipartiteness of orientation distance graphs and the representation...

Currently displaying 101 – 109 of 109

Previous Page 6