Immersione di sistemi parziali di m-cicli
Independent cycles and paths in bipartite balanced graphs
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
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
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.
Induced paths in twin-free graphs.
Infinite directed paths in locally finite digraphs
Infinite paths in locally finite graphs and in their spanning trees
The paper concerns infinite paths (in particular, the maximum number of pairwise vertex-disjoint ones) in locally finite graphs and in spanning trees of such graphs.
Interchangeability of relevant cycles in graphs.
Interval edge-coloring of caterpillars with hairs of arbitrary length
i-perfect m-cycle systems, m...19.
Isomorphic digraphs from powers modulo
Let be a prime. We assign to each positive number a digraph whose set of vertices is and there exists a directed edge from a vertex to a vertex if . In this paper we obtain a necessary and sufficient condition for .