A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs.
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 algorithm to recognize maximal generalized outerplanar graphs
In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.
A linear pseudo-Boolean viewpoint on matching and other central concepts in graph theory
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 linear upper bound in zero-sum Ramsey theory.
A Link Between Ordered Sets And Trees On The Rectangle Tree Hypothesis
A local limit theorem for the critical random graph.
A lower bound for Schur numbers and multicolor Ramsey numbers.
A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs
For a connected graph and a set with at least two vertices, an -Steiner tree is a subgraph of that is a tree with . If the degree of each vertex of in is equal to 1, then is called a pendant -Steiner tree. Two -Steiner trees are internally disjoint if they share no vertices other than and have no edges in common. For and , the pendant tree-connectivity is the maximum number of internally disjoint pendant -Steiner trees in , and for , the -pendant tree-connectivity ...
A lower bound for the irredundance number of trees
Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of Lemańska's result. ...
A lower bound for the number of distinct eigenvalues of some real symmetric matrices.
A lower bound for the number of edges in a graph containing no two cycles of the same length.
A Lower Bound for the Optimal Crossing-Free Hamiltonian Cycle Problem.
A lower bound for the packing chromatic number of the Cartesian product of cycles
Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9...
A lower bound on the independence number of a graph in terms of degrees
For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.
A magical approach to some labeling conjectures
In this paper, a complete characterization of the (super) edge-magic linear forests with two components is provided. In the process of establishing this characterization, the super edge-magic, harmonious, sequential and felicitous properties of certain 2-regular graphs are investigated, and several results on super edge-magic and felicitous labelings of unions of cycles and paths are presented. These labelings resolve one conjecture on harmonious graphs as a corollary, and make headway towards the...
A Markov chain approach to randomly grown graphs.
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 matrix representation of graphs and its spectrum as a graph invariant.