Embedding in distance degree regular and distance degree injective graphs
Downloads
DOI:
https://doi.org/10.26637/mjm104/015Abstract
The eccentricity \(e(u)\) of a vertex \(u\) is the maximum distance of \(u\) to any other vertex of \(G\).The distance degree sequence (dds) of a vertex \(u\) in a graph \(G=(V, E)\) is a list of the number of vertices at distance \(1,2, \ldots\), \(e(u)\) in that order, where \(e(u)\) denotes the eccentricity of \(u\) in \(G\). Thus the sequence \(\left(d_{i_0}, d_{i_1}, d_{i_2}, \ldots, d_{i_j}, \ldots\right)\) is the dds of the vertex \(v_i\) in \(G\) where \(d_{i_j}\) denotes number of vertices at distance \(j\) from \(v_i\). A graph is distance degree regular (DDR) graph if all vertices have the same dds. A graph is distance degree injective (DDI) graph if no two vertices have the same dds.
In this paper, we consider the construction of a DDR graph having any given graph \(G\) as its induced subgraph. Also we consider construction of some special class of DDI graphs.
Keywords:
Distance degree sequence, Distance degree regular (DDR) graphs, Almost DDR graphs, Distance degree injective(DDI) graphsMathematics Subject Classification:
05C12- Pages: 134-141
- Date Published: 01-10-2013
- Vol. 1 No. 04 (2013): Malaya Journal of Matematik (MJM)
J. Akiyama, K. Ando and D. Avis, Miscellaneous properties of equi-eccentric graphs, Convexity and Graph Theory, Proc. Conf. In Haifa, Israel, 1981, North-Holland, Amsterdam (1984), 13-23. DOI: https://doi.org/10.1016/S0304-0208(08)72802-0
Berge, C. Graphs and Hypergraphs, North Holland, Amsterdam and London, 1973.
G.S. Bloom, L.V. Quintas and J.W. Kennedy, Distance Degree Regular Graphs, The Theory and Applications of Graphs, 4th International conference, Western Michigan University, Kalamazoo, MI, May (1980), John Wiley and Sons, New York, (1981), 95-108.
G.S. Bloom, L.V. Quintas and J.W. Kennedy, Some problems concerning distance and path degree sequences, Lecture Notes in Math. 1018, Springer-Verlag, Berlin, (1983), 179-190. DOI: https://doi.org/10.1007/BFb0071628
G. Brinkmann, Fast generation of Cubic graphs, J. Graph Theory, 23(2)(1996), 139-149. DOI: https://doi.org/10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U
F. Buckley and F. Harary, Distance in Graphs, Addison Wesley, 1990.
F.C. Bussemaker, S. Cobeljic, D.B. Cvetkovic, J.J. Seidel, Computer investigation of cube Graphs, T.H. Report 76-WSK-01, Technological University Eindhoven, Netherlands, 1976.
C.R. Cook, Graphs associated with (0,1) - arrays, Thesis Project Report No. 18 (Doctoral dissertation), Univ. Iowa, 1970.
F.Y. Halberstam and L.V. Quintas, A note on tables of distance and path degree sequences for cubic graphs, presented at: Silver Jubilee Conference on Combinatorics, University of Waterloo, Waterloo, Canada, June 14 - July 2, 1982.
F. Harary, On the group of the decomposition of two graphs, Duke Math. J. 26(1959), 29-34. DOI: https://doi.org/10.1215/S0012-7094-59-02603-1
F. Harary and R.W. Robinson, The diameter of a graph and its complement, Amer. Math. Monthly, 92(1985), 211-212. DOI: https://doi.org/10.1080/00029890.1985.11971579
Medha Itagi Huilgol, H. B. Walikar, B. D. Acharya, On diameter three distance degree regular graphs, Advances and Applications in Discrete Mathematics, 7(1)(2011), 39-61.
Medha Itagi Huilgol, Rajeshwari M. and Syed Asif Ulla S., Distance degree regular graphs and their eccentric digraphs, International J. of Math. Sci. and Engg. Appls.(IJMSEA), 5(VI)(2011), 405-416.
Medha Itagi Huilgol, Rajeshwari M. and Syed Asif Ulla S., Products of distance degree regular and distance degree injective graphs, Journal of Discrete Mathematical Sciences and Cryptography, 15(4:5)(2012), 303- 314. DOI: https://doi.org/10.1080/09720529.2012.10698382
P. Martinez and L.V. Quintas, Distance degree injective regular graphs, Notes from New York Graph Theory Day VIII, New York Academy of Sciences (1984), 19-21.
J. Nieminen, The center problem in the product of graphs, Recent Studies in Graph Theory (1989), 201-205.
Nandakumar R. and K. R. Parthasarathy, Unique eccentric point graphs, Discrete Math., 46(1983), 69-74. DOI: https://doi.org/10.1016/0012-365X(83)90271-6
G. Sabidussi, Graph derivatives, Math.Z., 76(1961), 385-401. DOI: https://doi.org/10.1007/BF01210984
J. Volf, A small distance degree injective cubic graphs, Notes from New York graph theory day XIII, New York Academy of Sciences 31-32 (1987).
- NA
Similar Articles
- Manish Gupta, J.S. Bhullar, O.P. Vinocha, Error detection of irreducible cyclic codes on \(q\)-ary symmetric channel , Malaya Journal of Matematik: Vol. 1 No. 04 (2013): Malaya Journal of Matematik (MJM)
You may also start an advanced similarity search for this article.
Metrics
Published
How to Cite
Issue
Section
License
Copyright (c) 2013 MJM
This work is licensed under a Creative Commons Attribution 4.0 International License.
