Page 1

Displaying 1 – 11 of 11

Showing per page

Independent cycles and paths in bipartite balanced graphs

Beata Orchel, A. Paweł Wojda (2008)

Discussiones Mathematicae Graph Theory

Bipartite graphs G = (L,R;E) and H = (L’,R’;E’) are bi-placeabe if there is a bijection f:L∪R→ L’∪R’ such that f(L) = L’ and f(u)f(v) ∉ E’ for every edge uv ∈ E. We prove that if G and H are two bipartite balanced graphs of order |G| = |H| = 2p ≥ 4 such that the sizes of G and H satisfy ||G|| ≤ 2p-3 and ||H|| ≤ 2p-2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that for integers...

Independent Detour Transversals in 3-Deficient Digraphs

Susan van Aardt, Marietjie Frick, Joy Singleton (2013)

Discussiones Mathematicae Graph Theory

In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient...

Independent transversals of longest paths in locally semicomplete and locally transitive digraphs

Hortensia Galeana-Sánchez, Ricardo Gómez, Juan José Montellano-Ballesteros (2009)

Discussiones Mathematicae Graph Theory

We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.

Isomorphic digraphs from powers modulo p

Guixin Deng, Pingzhi Yuan (2011)

Czechoslovak Mathematical Journal

Let p be a prime. We assign to each positive number k a digraph G p k whose set of vertices is { 1 , 2 , ... , p - 1 } and there exists a directed edge from a vertex a to a vertex b if a k b ( mod p ) . In this paper we obtain a necessary and sufficient condition for G p k 1 G p k 2 .

Currently displaying 1 – 11 of 11

Page 1