On the minimal length of the longest trail in a fixed edge-density graph
A nearly sharp lower bound on the length of the longest trail in a graph on n vertices and average degree k is given provided the graph is dense enough (k ≥ 12.5).
On the number of complete subgraphs and circuits contained in graphs
On the number of cycles in a graph
On the number of cycles in -connected graphs.
On the number of representations of an element in a polygonal Cayley graph
We compute explicitly the number of paths of given length joining two vertices of the Cayley graph of the free product of cyclic groups of order k.
On the path number of a digraph.
On the permutations generated by cyclic shift.
On the resilience of long cycles in random graphs.
On the set of all shortest paths of a given length in a connected graph
On the stability for pancyclicity
A property P defined on all graphs of order n is said to be k-stable if for any graph of order n that does not satisfy P, the fact that uv is not an edge of G and that G + uv satisfies P implies . Every property is (2n-3)-stable and every k-stable property is (k+1)-stable. We denote by s(P) the smallest integer k such that P is k-stable and call it the stability of P. This number usually depends on n and is at most 2n-3. A graph of order n is said to be pancyclic if it contains cycles of all lengths...
On the Symbolic Evaluation of Determinants
On the tree graph of a connected graph
Let G be a graph and C be a set of cycles of G. The tree graph of G defined by C, is the graph T(G,C) that has one vertex for each spanning tree of G, in which two trees T and T' are adjacent if their symmetric difference consists of two edges and the unique cycle contained in T ∪ T' is an element of C. We give a necessary and sufficient condition for this graph to be connected for the case where every edge of G belongs to at most two cycles in C.
On the Turán properties of infinite graphs.
On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3.
On-line Ramsey theory.
On-line ranking number for cycles and paths
A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that for n ≥ 2. Here we show...
Onq-Power Cycles in Cubic Graphs
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.
Operations on graphs determining congruences on graphs
Optimal Cycles in Doubly Weighted Graphs and Approximation of Bivariate Functions by Univariate Ones.
Order of the smallest counterexample to Gallai's conjecture
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 with , which implies that Zamfirescu’s conjecture is true.