Displaying similar documents to “Edge-disjoint paths in permutation graphs”

A linear algorithm for the two paths problem on permutation graphs

C.P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

Similarity:

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.

Listing all plane graphs.

Yamanaka, Katsuhisa, Nakano, Shin-Ichi (2009)

Journal of Graph Algorithms and Applications

Similarity:

Edge-Transitive Lexicographic and Cartesian Products

Wilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang,...