On the interchange heuristic for locating centers and medians in a graph
On the intersections of longest cycles in a graph.
On the inverse eigenvalue problems: the case of superstars.
On the Laplacian spread of trees and unicyclic graphs
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...