A note on two circumference generalizations of Chvátal's Hamiltonicity condition
A path(ological) partition problem
Let τ(G) denote the number of vertices in a longest path of the graph G and let k₁ and k₂ be positive integers such that τ(G) = k₁ + k₂. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V₁ and V₂ such that τ(G[V₁] ) ≤ k₁ and τ(G[V₂] ) ≤ k₂. We show that several classes of graphs have this partition property.
A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs.
A proof of the two-path conjecture.
A remark on distances in products of graphs
A simple method for constructing small cubic graphs of girths 14, 15, and 16.
A simple proof of Whitney's Theorem on connectivity in graphs
In 1932 Whitney showed that a graph with order is 2-connected if and only if any two vertices of are connected by at least two internally-disjoint paths. The above result and its proof have been used in some Graph Theory books, such as in Bondy and Murty’s well-known Graph Theory with Applications. In this note we give a much simple proof of Whitney’s Theorem.
A Survey of the Path Partition Conjecture
The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.
A theorem for an axiomatic approach to metric properties of graphs
A traceability conjecture for oriented graphs.
A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs
A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ {3, . . . , n}. A vertex v ∈ V (G) is called super-heavy if the number of its neighbours in G is at least (n+1)/2. For a given graph H we say that G 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 that at least one of them is super-heavy. For a family of graphs H we say that G is H-f1-heavy, if G is H-f1-heavy for every graph...
A σ₃ type condition for heavy cycles in weighted graphs
A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least m; 2. w(xz) = w(yz) for every...
Acyclic numbers of graphs.
Adjacent vertex distinguishing edge colorings of the direct product of a regular graph by a path or a cycle
In this paper we investigate the minimum number of colors required for a proper edge coloring of a finite, undirected, regular graph G in which no two adjacent vertices are incident to edges colored with the same set of colors. In particular, we study this parameter in relation to the direct product of G by a path or a cycle.
Algebraic tools for the construction of colored flows with boundary constraints
We give a linear time algorithm which, given a simply connected figure of the plane divided into cells, whose boundary is crossed by some colored inputs and outputs, produces non-intersecting directed flow lines which match inputs and outputs according to the colors, in such a way that each edge of any cell is crossed by at most one line. The main tool is the notion of height function, previously introduced for tilings. It appears as an extension of the notion of potential of a flow in a planar...
Algebraic tools for the construction of colored flows with boundary constraints
We give a linear time algorithm which, given a simply connected figure of the plane divided into cells, whose boundary is crossed by some colored inputs and outputs, produces non-intersecting directed flow lines which match inputs and outputs according to the colors, in such a way that each edge of any cell is crossed by at most one line. The main tool is the notion of height function, previously introduced for tilings. It appears as an extension of the notion of potential of a flow in...
Algorithms for single link failure recovery and related problems.
Almost-Rainbow Edge-Colorings of Some Small Subgraphs
Let f(n, p, q) be the minimum number of colors necessary to color the edges of Kn so that every Kp is at least q-colored. We improve current bounds on these nearly “anti-Ramsey” numbers, first studied by Erdös and Gyárfás. We show that [...] , slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing [...] and for all even n ≢ 1(mod 3), f(n, 4, 5) ≤ n− 1. For a complete bipartite graph G= Kn,n, we show an n-color construction to color the edges...
Alpha-critical hypergraphs
Alspach's problem: The case of Hamilton cycles and 5-cycles.