 Applied Mathematics, 2011, 2, 705-710 doi:10.4236/am.2011.26093 Published Online June 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM On Eccentric Digraphs of Graphs Medha Itagi Huilgol*, Syed Asif Ulla S., Sunilchandra A. R. Department of Mat hematics, Ba ngal ore University, Bangalore, India E-mail: medha@bub.ernet.in Received March 11, 2011; revised April 9, 2011; accepted April 12, 2011 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. Keywords: Eccentric Vertex, Eccentric Degree, Eccentric Digraph, Degree Sequence,Eccentric Degree Sequence 1. Introduction A directed graph or digraph G consists of a finite nonempty set called vertex set with vertices and edge set of ordered pairs of vertices called arcs; that is represents a binary relation on VGEGEGVG. Throughout this paper, a graph is a symmetric digraph; that is, a digraph G such that implies If  is an arc, it is said that u is adjacent to v and also that v is adjacent from u. The set of vertices which are from (to) a given vertex v is denoted  ,uv EGvu E G,.,uvby and its cardinality is the out-degree  NuNuof v [in-degree of v]. A walk of length k from a vertex u to a vertex v in G is a sequence of vertices 012 1=,,,,,= kkuuuuu uv,uusuch that each pair 1ii is an arc of G. A digraph G is strongly connected if there is a u to v walk for any pair of vertices u and v of G. The distance d(u,v) from u to v is the length of a shortest u to v walk. The eccentricity e(v) of v is the distance to a farthest vertex from v. If ,=distu veuvudiGGGG we say that v is an eccentric vertex of u. We define whenever there is no path joining the vertices u and v. The radius rad(G) and diameter diam(G) are minimum and maximum ec- centricities, respectively. As in , the sequential join 123 k of graphs 12 is the graph formed by taking one copy of each of the graphs 12 and adding in additional edges from each vertex of i to each vertex in 1i, for 11,=stu v,,,kGG G,,,kGG GGG ik. Throughout this paper, means G and H are ='G Hisomorphic. The reader is referred to Buckley and Harary  and Chartrand and Lesniak  for additional, un- defined terms. Buckley  defines the eccentric digraph ED G of a graph G as having the same vertex set as G and there is an arc from u to v if v is an eccentric vertex of u. The paper  presents the eccentric digraphs of many classes of graphs including complete graphs, complete bipartite graphs, antipodal graphs and cycles and gives various interesting general structural properties of eccentric digraphs of graphs. The antipodal digraph of a digraph G denoted by AG, has the vertex set as G with an arc from vertex v in AG if and only if v is an antipodal vertex of u in G; that is .m G,=u vdist dia This notion of antipodal digraph of a digraph was introduced by Johns and Sleno  as an extension of the definition of the antipodal graph of a graph given by Aravamudhan and Rajendran . It is clear that AG is a subgraph of ED G, and =AGEDG if and only if G is self centered. In  Akiyama et al. have defined eccentric graph of a graph G, denoted by e, has the same set of vertices as G with two vertices u and v being adjacent in e if and only if either v is an eccentric vertex of u in G or u is an eccentric vertex of v in G, that is GG,=min ,GGdistu veev*Part of this paper  was presented at the International Conference on Emerging Trends in Mathematics and Computer Applications, MEPCO Schlenk Engineering College, Sivakasi, India (Dec. 2010) and had appeared in the Proceedings of the same. Gu. Note that is the underlying graph of eGGED . In  Boland and Miller introduced the concept of the M. I. HUILGOL ET AL. 706 if aeccentric digraph of a digraph. In  Gimbert et al. have proved that=eGnd only if G is self-centered. In the same paper, the authors have characterized eccen- tric digraphs in terms of complement of the reduction of G, denoted by EDG G Given a digraph G of order n, a reduction of G, doted by G, is derived from G by enremoving all its arcs incident from vertices with out- degree 1n. Note that )(GED is a subgraph of .G In  , Gmbert et al. died on the behaviofihave stuour se. The iterated se- G and t . Basic Results this section we list some results which are quite ph has at least on2. There exists no directed cycle in an eccen- tra directed cycle with edge being didges cther edquences of iterated eccentric digraphs. Given a positive integer 2k , the thk iterated eccentric digraph of G is writte 1kkDGED EDG, where 0=ED GGentric with the smallest integer numbers 0>p and 0t such that  =tpEDGED  We cathe period ofantities are denoted p(G) and t(G) respectively. In [8,10] Boland et al. have discussed many interesting results about eccentric digraphs. Also they have listed open problems about these graphs. One of these open problems is being discussed mainly in this paper. We have characterized graphs with specified maximum degree such that =EDGG . n asE of eccil of G; t =1EDdigratG.qu and  =GED Gphs concerns ll p hese quencethe ta2 Inevident for eccentric digraphs of graphs. Remark 1. Since every vertex in a grae vertex at eccentric distance it follows that every vertex in an eccentric digraph will have out degree at least one. Remark ic digraph. Let C be uve 1rectedom uv as shown below in Figur . The other ean be bidirectional. If all the o frges except uv are bidirectional then a symmetric edge 1vy indicates the equality of eccentric values of v and ikewise  1y. L==neccyecc x12==ecceccyy. Also edgexusymmHence,  =ecc ueccxeccecc u. This coarc u to tha is existence of etric. 1the directed . So also,  ===veccyecc xtradicts the v as u being tail has less eccentricity as comparedt of . The same argument can be extended to a directednv cyr a graph to symmetric cycle having a pecle with more than one directed arc, as the eccen- tricities go on increasing in the same direction. The above two conditions are not sufficient fo be an eccentric digraph. For example consider andant vertex adjacent to one of the vertices on the cycle. The pendant vertex having in-degree zero and out-degree one as in Figure 2. Vertex ix is at eccentric distance from. Let be upv adjaceno u and lying on the eccentric ath con- necting u and it tx. All the vertices in the graph except ixare adistanc atmost 1n from u, where n is eccentricity of u. This implies v bng adjacet to u will have eccentricity n. Buv lying on the metric circle can have eccentricity 1n. There- fore the above graph cannot be an eccentriaph. Also we give a counter example for a problem git ethe symei nt c digrven in2.2 (p. 41) : If G is self-centered w  , as follows: Problem 3, Ex. ith radius 2 , then G is self-centered with radius 2. Counter Exampleonsider 7C, join the vertice a: Cst distance 2 in .7C Let G be tresulting graph with he =2rad G. Considering G, we observe that 7GC; that is G is self-centered of radius 3. . Grahs with Isomorphic Eccen3ptric case of undirected graphs, Buckley  proved that the Digraph In Figure 1. Directed cycle C. Figure 2. Directed cycle with unidirectional edge u-xi. Copyright © 2011 SciRes. AM M. I. HUILGOL ET AL.707 ecc - entric digraph of a graph G is equal to its complement, ()= ,ED GGif and ly if G is either a self-centeradius two or G is the union of 2k complete graphs. In , Gimbert et al. have that the eccentric digraph ED G is symmetric if and only if G is self centered. Here we are looking at gronred graph of aphs which have their ecor which Odd cycles are graphs with minimum nu radius 3,provedcentric digraphs isomorphic to themselves. So by Gimbert’s result these graphs are self-centered graphs. In this section we consider self-centered, undirected graphs. The following observations are easily justified. Remark 3. Odd cycles is a class of graphs f=.GG . EDRemark 4mber of edges and maximum eccentricity on given number of vertices such that =.EDGG Remark 5. For a self-centewithred graph G  the complement G is self-centered with radius equ to two. Hence alGG, and GG, and\ED G is isomorphic to araph o subgf G. Fth urther,ing Buckley’s result , we can say at by us==EDGGG . That is if =,ED GED G then G=EDG. k 6. Complete graphs is another class of grRemaraphs for which =EDGG . Remark 7. It is easy to see that for graphs upto order 7, the only graphs for which =EDGG , are 23455677,,, ,,,,KKKKCKKCic g. hraphs havRemark 8. Two isomorpe their eccen- trhown inn Figure 3, we give a pair ofraph with ra- diic digraphs isomorphic, but the converse need not be true always. As an example, as s non-isomorphic, self-centered graphs with same eccentricity having one eccentric digraph. Lemma 9. Let G be a self-centered gus 2, then =EDG if and only if G is self- complementary.Proof. Given self-centeG red graph be self-com- plGementary with radius 2. Then by Buckley’s cha- racterization theorem , ==DGGG . Conversley, consider a self-centered gra with =EDGG . Then, Eph of radius 2,=,EDGG that is ==GEDGLemma 10. G. Het.  nce tresul with eccen- trhe All self-centered graphs Gicity greater than or equal to 3 with Ghaving =1, =1,periodtail satisfies th condition e=ED Ga self-centered graph G. with eccen- Proof. Let G be tricity 3.Then G is self-centered graph with eccen- tricity al to 2. nce, equHe==;EDGGG that is 2EDGED G. If Gand tail has , that is =1period 1= ED then 2ED GG2ED GGGED . But 2EDGED G Figure 3. ED(G) = ED(H). 2=ED GEDGEDGG. Hence the result. For connected graph to be isomorphic to  G ED Gld not be rathy cember of the necessary c shounique eccentric node as defined by Parthasaand Nandakumar , for ssary condition is that thfor evv of a grfr oasing order. ondition is that the graphugraph . Alsoe thGEDG, the ne- egree say ery vertex of dk, there must exist anoer vertex with k nu eccentric vertices. This can be defined as eccentric degree of a vertex. Definition 11. For a vertex aph G is defined to be the number of vertices at eccentric distance om v. Also the eccentric degree sequencef a graph is defined as a listing of eccentric degrees of vertices written in non-increSo for =ED GG, the eccentric degree sequen of G should be equal to the degree sequence of G. But this condition is not sufficient as seen in the example below, depicted as Figure 4. Here both G and ceED G have their degree seqence and eccentric degree sequences as 493,2 , but ED GG. Next, we consider self-centered graphs with given maximum degree G. By , 22,Gpr for a self-centered graph G with radius r. Our next result shows that there is no possibility of having a graph with =GEDG, with =22prG. Proposition 12. There does not exist a graph G with =22Gpr, hat such t=G. ED GProof. Let G be a self-centered graph with =22Gpr Let uVG such that deg u implies =2pr2. Partitntoion the vertex set i sets lying Copyright © 2011 SciRes. AM M. I. HUILGOL ET AL. 708 then 1rx will have u as the oy eccentric veex, a ntradiction. imilar contradiction is arrived if 1rnl rtcoSx is adjacent to both 2rx and 21rx Same argum can be appliedn case of ent iFigure 4. G and ED(G) having same eccentric degree se-quence and degre e se quence, but ED(G) ≇ G. at distance fromand name them as i u , 1iAir. Since 2, =2deg pur 2. As G is 2=1 rpAself-centered, it cannot contain a cut-vertex and hence 2, 2iAir. Hence, 22r vertices are needed to onsideration,tices. Hencesatisfyh under c with the cnditionsf tt possible to constro ohe grapt a grapbut we have 22=23ppr r ver, it is nouch =EDGG , with =22Gpr. connectecentered graph G with =21Gpr is isomorphic to its eccentric digraph if and only i is of the form 2221,2ppr  with structure Theorem 13. Ad self-f its degree sequence1212222 ,prKKFKKHKHKHr times  where F is the gjoining one vertex of raph obtained by 21 to prK one vertex of 2K and remaining 2pr vertices to one vertex of 2K, and H is the 1factor removed from successive 22KK. Proo Let G be a self-centered graph with =21Gpr. Let u be a vertex of G with 21p r. As seen in the above Lemma f. each =deg u,iA should contain at least two vertices each, for G tosatisfy =GEDG, wicenths self-terednnot ining ess andma be22r vertirat least two ieing unique entric node graph. Since the ree to be ditributed into 1r sets with ach set, it follows that each ieccces an A has vertices. Let ththe set kexactly twoe vertices in A be labelled 1kx and 2kx for all k, 2kr. Since G has no cutvertex, 11rx be adjacent to at least one vertexrshould of A, let us say, to 1rx and similarly let 21rx be adjacent to 2rx. Degree of 1rx is at le22ast tw be adj toof o, so it canacent any 1, rrxx or both. 2rx. Therefore, 1rx and 2rx are mutually adjahave degree at least two. There are two ps 1 P an2ijP where iicatht be equal to j. r cases are proved as follows: Cla 1: The vertices ent td oOtheim o 1111 1jx1 111122331 111 1111111 211=, , , , , , ,,,,,, ,,,,,,,;,=1kkkkkk rrrrrPuexexexeexex xexexij  and 22 22112 ,, , , iji ijPuexe23322222211 1122222211=, , ,, ,,,,,,, ,,,,;2,21, kkkkkkrrrrrxexexexexxexexijpr   i need n11kx are adjacent to either 1kx 2kxSuppose, 1rx is adjacent to 21rx, or , buProof ox belt not both; for. f the claimvertex eacverteonging to all : Since , 21kkrG has no cut h kA, 21kr, is adjacent to at least one vertex in 1kA and 1kA. Without loss gene- rality let each vertex 11kx be adjacent to 1kx, for all , 21krk. Let us cder konsiA, with vertices 1kx and 2k x. Let 11kx be adjacent to 2kx aloithng w 1kx. Then eccentricity of 11kx can be at most 1r as any vertex lying on the p 1an be at most at a distance 1rath P or 2ijP c from 1k1x. And any vertex on the path ijP2 can be at most at a distance of 2r fr 2komx. In any case if 11kx is adjacent to both2k x and 1kx then ceases to be seentered, a contradiction and hence proof of the claim. Claim 2: Each , 2i Gthelf-c1Akr is independent, that is, ,2=iAKPhe re. roof of the claim: First we prove tsult for 1rA. If the verti11rces x and 21rx beloing to1rng A are adjacent then 11rx will have u as the only eccentric vertex, a contradicti proat on ves th12rA=KFor any other . kA, 2kr2, if 1kx and 2kx are adjacent then, eccentricity of 1kx and 2kx will t most r − 2 as vertices on P or ijP2 will be at distance at most r − 2 m 1kbe a1frox or 2kx and hence for all k, 2iClaim 3: 121, =krAK. 2x and 22x do not haneve comon ors inm ighb 1A. Proof of the claim: As in case of the veces of 1rrtiA, the vertices 12x and 22x of 2A will have their eccentricity equal to 1r ifhey have a common tneighbor in 1A, h1ence . th claimeClaim 4: 2x is adjacent to 11x and 22x is adjacent to all er p-othtices of Proof of taim : If 2r verhe clA.1 12x is adjacent to Copyright © 2011 SciRes. AM M. I. HUILGOL ET AL.709 =1=1 , 1<<2kikkxip r, then two vertices 2rx and 1r2x have eccentric degree k + 1, but only one vertex 12x has del dicgree equa 1k, a contration. If 12 tox and 22x have dege k each ,that is if 2k1re=2 1pr, then rx, r2x, 1r1x and 21rx have eccentric degree equal to+ 1, but only two k vertices12x and 22x haHence,ve de 1gree k + 1. 2x is adjacent to 1x1not a and 1x21, 1<<2i djacent to xip r. Finding the etric degree of all ccenrtices of G we see that, ecc. degve1=2, 11kxkr and ecc.deg 1=2ky, except for 11rx, where 11kkyNx. Silarly, ecc. deg2=mi2,k 11xkr and ecc.deg 2y2gr2=2k, where. Hence, the eccentric de- kkyNxence of Gee sequence of G is 2221,2ppr  , which is same as that of degree sequClaim 5: . 121=pr. Proof Wet for any twvertices AKof the claim: show thao 1tx and 1sx where 1,ts  are not , 1, 2tsp reed to consadjacentn. Here we ider two possibilities: Case 1): 112txNx and 221sxNx Case 2): 212txNx and 1s22xNx In case 1), 1tx will have only one eccentric vertex, a contradiction. In case 2), deg1tx,deg 13then only the ver- tic 1sx es rx or 2rx of rA and 11rx or 21rx of 1rA the cartof along pa r , sin have ve as ecices 2ijPA1nccentric vertices, ths 1P oe 12x and 22x t shcodo noare a mmon neighr in 1boA , as claimed in 3. By Claim 4at 1, we see th2x is adjacent to 11x and 2x 2th vertis adjacent to all oer pices of 1− 2rA, implies t when degrees ttha of 1x and 1sx c aemcedegree other i vehe fof Cgivmemark 1tices re changed by mak- ing th adjant, thccentriny overtex of does not change, hence we will not be able to get =E G a contradion pros the claim. Referring all the claims we conclude tat e ef aGDG, ct is of thrm defined in the statement othe theorem. onverse is easy to observe that if G is as en in the statement of the theore, then =GG .  In the next result we consider a particular case of graphs with =EDGG , that is, odd cycles. R a labelled 21,1nCn, two verED4. In,ijv are at eccentric distance in 21nED C, if and onvly if ,=2Gijdvv or n1n2. Remark 15. For unlabelled itti odd cycles,eraons of can be packed into21nED C nK,131=22ns, nED G, whereas, 2rad Cn1=n. In case of labelled odd cyclesnce of ED(G)'s e packed into K,pif the permutatumber of the sequecan bion on p n defined by vertices 1=1, 2=2, =1,2,3,,;1=2 2,=1,2,,ffirii rfir iir 23, since there are is a product of three cyclicns of length respectively. permutatio,r1, r, Proposition 16. There exists a self-centered graph G, such that =EDGG , containing an odd cycle. Proof. Let be pC be a cycle, whose vertices arelabeled as . Let . Define a function onices 1, 2, 3, the setvert,p of =1,2,3, ,Spof pC as  21=1, 112.fipiip1=1, 2=232,112,ffipi ip  Now, we partition of set of vertices of pC into 123,, mS, , SSS ere, wh12 1= 2,, 2, SSf S where n is the least positteg21,=2, 2,, 2nf five iner such that 2=12nf whereas2nf is obtained by applyi ngf on n2, times. Similarly,  2=, , ,, , mmSlflfl flS S 1123 1 ,mlS S where is the least positive integer such that m =1mfll. It is clear that 123 =mSSSS S and =, 1,ij j,i jmiSS . Now, for each vertex iS we fine sets of vertices not in of depC by  2=, ,,iii iijj jjSflflfln for each , and whose adjacencies are to the ertices of i=1,2,3,j vpC defined by: If gfl, when is adjacent 1lpto hfl, then, gijfl is adjacent to glNf , hijfl and hijfl is adjac to  ,hgilf lent j; othese, Nfgijflis adjacent to gNfl and hrwi ijfl is acent to djahNfl . So we get a self-cegraph withntered radius 12p,isfying =ED GG savertices t, as l on pC and respective , 1ijmfllp, e same distance from ther vertices in the graph. By Remark 15, we get hav oG.  Fng is an ee of a self-cente ED Gollowradius own iing i xampl4, as shn Figure 5, satisfyred graph withED GG, with 9C, asSo base. =1,2,S ,9 and 45,,SS12=,,pVC SS, where 3S12=1,=2,54, =7.SS S 345,8, =, =3,6,9S SCopyright © 2011 SciRes. AM M. I. HUILGOL ET AL. Copyright © 2011 SciRes. AM 710 Figure 5. ED(G) ≅ G. For we have , 14,iSi 11121321111 231222223333123132334142423123=1, =1, =1; =2,5,8, =2,5,8 , =2,5,8; =4, =4, =4; =7, =7, =7.SSSSSSSSSSSS 3 4. References . I. Huilgol, Sd A. R. Sunilchandra, “Oncentric Digraphs of Graphs,” Proceedings of the In-ternational Conference on Emerging Trends in Mathe-matics and Computer Applications, MEPCO Schlenk Enege, Sivakasi, 16-18 December 2010, pp. 41-44. gineering Coll F. Buckley and F. Harary, “Distance in Graphs,” Addi-son-Wesley, Redwood City, 1990.  G. Chartrand and L. Lesniak, “Graphs and Digraphs,” 3rd Edition, Chapman & Hall, London, 1996.  F. Buckley, “The Eccentric Digraph of a Graph,” Con-gressus Numerantium, Vol. 149, 2001, pp. 65-76.  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  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  J. Akiyama, K. Ando and D. Avis, “Eccentric Graphs,” Discrete Mathematics, Vol. 56, No. 1, 1985, pp. 1-6. 8doi:10.1016/0012-365X(85)90188- (AWOCA 2001), e Institute of Com- J. Boland and M. Miller, “The Eccentric Digraph of a Digraph,” Proceedings of the 12th Australasian Work-shop of Combinatorial AlgorithmsFreiburg, 3-7 September 2001, pp. 66-70.  J. Gimbert, M. Miller, F. Ruskey and J. Ryan, “Iterationsof Eccentric Digraphs,” Bulletin of thbinatorics and Its Applications, Vol. 45, 2005, pp. 41-50.  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  R. Nandakumar and K. R. Pathasarathy, “Unique Eccen-tric Point Graphs,” Discrete Mathematics, Vol. 46, No. 1, 1983, pp. 69-74. doi:10.1016/0012-365X(83)90271-6  M. A. S. Ulla anEc -