|
|||||
|
|
Second Neighborhood via First Neighborhood in Digraphs |
|
| Authors: | Guantao Chen Jian Shen Raphael Yuster |
| Institution: | Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA, gchen@mathstat.gsu.edu, US Department of Mathematics, Southwest Texas State University, San Marcos, TX 78666, USA, US Department of Mathematics, University of Haifa-Oranim, Tivon 36006, Israel, IL |
| Abstract: | Let D be a simple digraph without loops or digons. For any v ? V(D) v\in V(D) , the first out-neighborhood N+(v) is the set of all vertices with out-distance 1 from v and the second neighborhood N++(v) of v is the set of all vertices with out-distance 2 from v. We show that every simple digraph without loops or digons contains a vertex v such that |N++(v)| 3 g|N+(v)| |N^{++}(v)|\geq\gamma|N^+(v)| , where % = 0.657298... is the unique real root of the equation 2x3 + x2 -1 = 0. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |