<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue1" %>
Second Neighborhood via First Neighborhood in Digraphs
G. Chen1, J. Shen2, and R. Yuster3
1Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA
gchen@mathstat.gsu.edu
2Department of Mathematics, Southwest Texas State University, San Marcos, TX 78666, USA
3Department of Mathematics, University of Haifa-Oranim, Tivon 36006, Israel
Annals of Combinatorics 7 (1) p.15-20 March, 2003
AMS Subject Classification: 05C38
Abstract:
Let D be a simple digraph without loops or digons. For any , the first out-neighborhood is the set of all vertices with out-distance 1 from v and the second neighborhood 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 , where is the unique real root of the equation .
Keywords: digraph, cycle, in-degree, out-degree, neighborhood

References:

1. M. Behzad, Minimally 2-regular digraphs with given girth, J. Math. Soc. Japan 25 (1973) 1每6.

2. M. Behzad, G. Chartran, and C. Wall, On minimum regular graphs with given girth, Fund. Math 69 (1970) 227每231.

3. J.C. Bermond, 1-graphs r谷guliers de girth donn谷, Cahiers du C.E.R.O. Bruxelles 17 (1975) 123每135.

4. J.A. Bondy, Counting subgraphs: a new approach to the Caccetta-Häggksvist conjecture, Discrete Math. 165/166 (1997) 71每80.

5. L. Caccetta and R. Häggkvist, On minimal digraphs with given girth, In: Proc. 9th Southeastern Conf. on Combinatorics, Graph Theory and Computing, 1978, pp. 181每187.

6. V. Chv芍tal and E. Szemer谷di, Short cycles in directed graphs, J. Combin. Theory, Ser. B 35 (1983) 323每327.

7. N. Dean and B.J. Latka, Squaring the tournament 〞 an open problem, Congr. Numer. 109 (1995) 73每80.

8. D.C. Fisher, Squaring a tournament: a proof of Dean's conjecture, J. Graph Theory 23 (1) (1996) 43每48.

9. M. de Graaf, A. Schrijver, and P.D. Seymour, Directed triangles in directed graphs, Discrete Math. 110 (1992) 279每282.

10. Y.O. Hamidoune, An application of connectivity theory in graphs to factorization of elements in groups, Europ. J. Combin. 2 (1981) 349每355.

11. Y.O. Hamidoune, A note on the girth of digraphs, Combinatorica 2 (1982) 143每147.

12. Y.O. Hamidoune, A note on minimal directed graphs with given girth, J. Combin. Theory, Ser. B 43 (1987) 343每348.

13. C.T. Ho芍ng and B. Reed, A note on short cycles in digraphs, Discrete Math. 66 (1987) 103每107.

14. Y. Kaneko and S.C. Locke, Notes on Seymour's second neighborhood conjecture, In: Abstracts of 33 Southeastern International Conference on Combin. Graph Theory, and Computing, Baton Rouge, 2002.

15. T. Nishimura, Short cycles in digraphs, Discrete Math. 72 (1988) 295每298.

16. J. Shen, Directed triangles in digraphs, J. Combin. Theory, Ser. B 74 (2) (1998) 405每407.

17. J. Shen, On the girth of digraphs, Discrete Math. 211 (2000) 167每181.

18. J. Shen, On the Ceccetta-Häggkivist conjecture, Graphs Combin. 18 (2002) 645每654.