Ordinary and directed combinatorial homotopy, applied to image analysis and concurrency.
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...
Several authors have studied the graphs for which every edge is a chord of a cycle; among 2-connected graphs, one characterization is that the deletion of one vertex never creates a cut-edge. Two new results: among 3-connected graphs with minimum degree at least 4, every two adjacent edges are chords of a common cycle if and only if deleting two vertices never creates two adjacent cut-edges; among 4-connected graphs, every two edges are always chords of a common cycle.
In [3], Faudree and Gould showed that if a 2-connected graph contains no and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.
It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required. A possibly ‘intermediate’ variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of ∩(n1/k) on the growth rate.
We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), being the distance of u and v on a hamiltonian cycle of G.
In this note, we consider the partition of a graph into cycles containing a specified linear forest. Minimum degree and degree sum conditions are given, which are best possible.
For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n...
A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.