A characterization of geodetic graphs
A characterization of the set of all shortest paths in a connected graph
Let be a (finite undirected) connected graph (with no loop or multiple edge). The set of all shortest paths in is defined as the set of all paths , then the lenght of does not exceed the length of . While the definition of is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of : a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...
A conjecture on cycle-pancyclism in tournaments
Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote , the number of arcs that γ and Cₖ have in common. Let and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave...
A construction of geodetic blocks
A decomposition of gallai multigraphs
An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees...
A density result for random sparse oriented graphs and its relation to a conjecture of Woodall.
A Family of Path Properties for Graphs.
A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs
Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] mindG(u),dG(v)≥n+12 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity...
A Gessel--Viennot-type method for cycle systems in a directed graph.
A graph and its complement with specified properties. III: Girth and circumference.
A Hamiltonian property of connected sets in the alternative set theory.
A linear algorithm for the two paths problem on permutation graphs
The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.
A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...
A lower bound for the number of edges in a graph containing no two cycles of the same length.
A matching and a Hamiltonian cycle of the fourth power of a connected graph
The following result is proved: Let be a connected graph of order . Then for every matching in there exists a hamiltonian cycle of such that .
A metric for graphs
A modification of the median of a tree
The concept of median of a tree is modified, considering only distances from the terminal vertices instead of distances from all vertices.
A monotone path in an edge-ordered graph.
A new approach to chordal graphs
By a chordal graph is meant a graph with no induced cycle of length . By a ternary system is meant an ordered pair , where is a finite nonempty set, and . Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set , a bijective mapping from the set of all connected chordal graphs with onto the set of all ternary systems satisfying the axioms (A1)–(A5) is...
A new proof of a characterization of the set of all geodesics in a connected graph