On Eccentric Digraphs of Graphs

ABSTRACT

The eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a graph (digraph) G is the digraph that has the same vertex as G and an arc from u to v exists in ED(G) if and only if v is an eccentric vertex of u in G. In this paper, we have considered an open problem. Partly we have characterized graphs with specified maximum degree such that ED(G) = G.

The eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a graph (digraph) G is the digraph that has the same vertex as G and an arc from u to v exists in ED(G) if and only if v is an eccentric vertex of u in G. In this paper, we have considered an open problem. Partly we have characterized graphs with specified maximum degree such that ED(G) = G.

KEYWORDS

Eccentric Vertex, Eccentric Degree, Eccentric Digraph, Degree Sequence, Eccentric Degree Sequence

Eccentric Vertex, Eccentric Degree, Eccentric Digraph, Degree Sequence, Eccentric Degree Sequence

Cite this paper

nullM. Huilgol, S. Asif Ulla S. and S. A. R., "On Eccentric Digraphs of Graphs,"*Applied Mathematics*, Vol. 2 No. 6, 2011, pp. 705-710. doi: 10.4236/am.2011.26093.

nullM. Huilgol, S. Asif Ulla S. and S. A. R., "On Eccentric Digraphs of Graphs,"

References

[1] M. I. Huilgol, S. A. S. Ulla and A. R. Sunilchandra, “On Eccentric Digraphs of Graphs,” Proceedings of the In-ternational Conference on Emerging Trends in Mathe-matics and Computer Applications, MEPCO Schlenk En-gineering College, Sivakasi, 16-18 December 2010, pp. 41-44.

[2] F. Buckley and F. Harary, “Distance in Graphs,” Addison-Wesley, Redwood City, 1990.

[3] G. Chartrand and L. Lesniak, “Graphs and Digraphs,” 3rd Edition, Chapman & Hall, London, 1996.

[4] F. Buckley, “The Eccentric Digraph of a Graph,” Congressus Numerantium, Vol. 149, 2001, pp. 65-76.

[5] G. Johns and K. Sleno, “Antipodal Graphs and Digraphs,” International Journal of Mathematics and Mathematical Sciences, Vol. 16, No. 3, 1993, pp. 579-586. doi:10.1155/S0161171293000717

[6] R. Aravamudhan and B. Rajendran, “On Antipodal Graphs,” Discrete Mathematics, Vol. 49, No. 1, 1984, pp. 193-195. doi:10.1016/0012-365X(84)90117-1

[7] J. Akiyama, K. Ando and D. Avis, “Eccentric Graphs,” Discrete Mathematics, Vol. 56, No. 1, 1985, pp. 1-6. doi:10.1016/0012-365X(85)90188-8

[8] J. Boland and M. Miller, “The Eccentric Digraph of a Digraph,” Proceedings of the 12th Australasian Workshop of Combinatorial Algorithms (AWOCA 2001), Freiburg, 3-7 September 2001, pp. 66-70.

[9] J. Gimbert, M. Miller, F. Ruskey and J. Ryan, “Iterations of Eccentric Digraphs,” Bulletin of the Institute of Combinatorics and Its Applications, Vol. 45, 2005, pp. 41-50.

[10] J. Boland, F. Buckley and M. Miller, “Eccentric Digraphs,” Discrete Mathematics, Vol. 286, No. 1-2, 2004, pp. 25-29. doi:10.1016/j.disc.2003.11.041

[11] R. Nandakumar and K. R. Pathasarathy, “Unique Eccentric Point Graphs,” Discrete Mathematics, Vol. 46, No. 1, 1983, pp. 69-74. doi:10.1016/0012-365X(83)90271-6

[1] M. I. Huilgol, S. A. S. Ulla and A. R. Sunilchandra, “On Eccentric Digraphs of Graphs,” Proceedings of the In-ternational Conference on Emerging Trends in Mathe-matics and Computer Applications, MEPCO Schlenk En-gineering College, Sivakasi, 16-18 December 2010, pp. 41-44.

[2] F. Buckley and F. Harary, “Distance in Graphs,” Addison-Wesley, Redwood City, 1990.

[3] G. Chartrand and L. Lesniak, “Graphs and Digraphs,” 3rd Edition, Chapman & Hall, London, 1996.

[4] F. Buckley, “The Eccentric Digraph of a Graph,” Congressus Numerantium, Vol. 149, 2001, pp. 65-76.

[5] G. Johns and K. Sleno, “Antipodal Graphs and Digraphs,” International Journal of Mathematics and Mathematical Sciences, Vol. 16, No. 3, 1993, pp. 579-586. doi:10.1155/S0161171293000717

[6] R. Aravamudhan and B. Rajendran, “On Antipodal Graphs,” Discrete Mathematics, Vol. 49, No. 1, 1984, pp. 193-195. doi:10.1016/0012-365X(84)90117-1

[7] J. Akiyama, K. Ando and D. Avis, “Eccentric Graphs,” Discrete Mathematics, Vol. 56, No. 1, 1985, pp. 1-6. doi:10.1016/0012-365X(85)90188-8

[8] J. Boland and M. Miller, “The Eccentric Digraph of a Digraph,” Proceedings of the 12th Australasian Workshop of Combinatorial Algorithms (AWOCA 2001), Freiburg, 3-7 September 2001, pp. 66-70.

[9] J. Gimbert, M. Miller, F. Ruskey and J. Ryan, “Iterations of Eccentric Digraphs,” Bulletin of the Institute of Combinatorics and Its Applications, Vol. 45, 2005, pp. 41-50.

[10] J. Boland, F. Buckley and M. Miller, “Eccentric Digraphs,” Discrete Mathematics, Vol. 286, No. 1-2, 2004, pp. 25-29. doi:10.1016/j.disc.2003.11.041

[11] R. Nandakumar and K. R. Pathasarathy, “Unique Eccentric Point Graphs,” Discrete Mathematics, Vol. 46, No. 1, 1983, pp. 69-74. doi:10.1016/0012-365X(83)90271-6