TITLE

A Contribution to the Second Neighborhood Problem

AUTHOR(S)
Ghazal, Salman
PUB. DATE
September 2013
SOURCE
Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1365
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Seymour's Second Neighborhood Conjecture asserts that every oriented graph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. It is proved for tournaments, tournaments missing a matching and tournaments missing a generalized star. We prove this conjecture for classes of oriented graphs whose missing graph is a comb, a complete graph minus two independent edges, or a cycle of length 5.
ACCESSION #
89806006

 

Related Articles

  • UNDERLYING GRAPHS OF 3-QUASI-TRANSITIVE DIGRAPHS AND 3-TRANSITIVE DIGRAPHS RUIXIA WANG, SHIYING WANG. RUIXIA WANG; SHIYING WANG // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p429 

    A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). César Hernández-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation....

  • On Sullivan's conjecture on cycles in 4-free and 5-free digraphs. Liang, Hao; Xu, Jun // Acta Mathematica Sinica;Jan2013, Vol. 29 Issue 1, p53 

    For a simple digraph G, let β( G) be the size of the smallest subset X ⊆ E( G) such that G−X has no directed cycles, and let γ( G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This...

  • SOME REMARKS ON THE STRUCTURE OF STRONG k-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR; MONTELLANO-BALLESTEROS, JUAN JOSÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p651 

    A digraph D is k-transitive if the existence of a directed path (v0, v1, ..., vk), of length k implies that (v0, vk) ∈ & A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an...

  • Characterization of Line Sidigraphs. Sampathkumar, E.; Subramanya, M. S.; Reddy, P. Siva Kota // Southeast Asian Bulletin of Mathematics;2011, Vol. 35 Issue 2, p297 

    A sigraph (sidigraph) is an ordered pair S = (G; σ) (S = (D; σ)), where G = (V, E) (D = (V, A) is a graph (digraph) called the underlying graph (underlying digraph) of S and σ : E → {+, -} (&sigma: A → {+, -}) is a function. The line sigraph (line sidigraph) of a sigraph...

  • Rainbow Connection in 3-Connected Graphs. Li, Xueliang; Shi, Yongtang // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1471 

    An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc( G), is the smallest number of colors that are needed in order to make G rainbow connected. In this...

  • Neighborhood Unions for the Existence of Disjoint Chorded Cycles in Graphs. Gao, Yunshu; Li, Guojun; Yan, Jin // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1337 

    A chorded cycle is a cycle with at least one chord. We prove that if G is a simple graph with order n ≥ 4 k and $${|N_G(x)\cup N_G(y)|\geq 4k+1}$$ for each nonadjacent pair of vertices x and y, then G contains k vertex-disjoint chorded cycles. The degree condition is sharp in general.

  • $$\varPi $$ -Kernels in Digraphs. Galeana-Sánchez, Hortensia; Montellano-Ballesteros, Juan // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2207 

    Let $$D=(V(D), A(D))$$ be a digraph, $$DP(D)$$ be the set of directed paths of $$D$$ and let $$\varPi $$ be a subset of $$DP(D)$$ . A subset $$S\subseteq V(D)$$ will be called $$\varPi $$ -independent if for any pair $$\{x, y\} \subseteq S$$ , there is no $$xy$$ -path nor $$yx$$ -path in...

  • BROKEN CIRCUITS IN MATROIDS--DOHMEN'S INDUCTIVE PROOF. KORDECKI, WOJCIECH; ŁYCZKOWSKA-HANĆKOWIAK, ANNA // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 3, p599 

    Dohmen [4] gives a simple inductive proof of Whitney's famous broken circuits theorem. We generalise his inductive proof to the case of matroids.

  • Path-Bicolorable Graphs. Brandst�dt, Andreas; Golumbic, Martin; Le, Van; Lipshteyn, Marina // Graphs & Combinatorics;Nov2011, Vol. 27 Issue 6, p799 

    In this paper, we introduce the notion of path-bicolorability that generalizes bipartite graphs in a natural way: For k = 2, a graph G = ( V, E) is P -bicolorable if its vertex set V can be partitioned into two subsets (i.e., color classes) V and V such that for every induced P (a path with...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics