Perfect codes in some products of graphs

Samane Bakaein, Mostafa Tavakoli, Freydoon Rahbarnia

Abstract


A r-perfect code in a graph G = (V(G),E(G)) is a subset C of V(G) for which the balls of radius r centered at the vertices of C form a partition of V(G). In this paper, we study the existence of perfect codes in corona product and generalized hierarchical product of graphs where the cardinality of U is equal to one or two. Also, we give some examples as applications of our results.


Keywords


graph, perfect code, corona product, hierarchical product, generalized hierarchical product

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.15

References

G. Abay-Asmerom, R.H. Hammack and D.T. Taylor, Perfect r-codes

in strong products of graphs, Bull. Inst. Combin. Appl. 55 (2009), 66--72.

C. Adiga, Rakshith B. R., K. N. S. Krishna, Spectra of extended neighborhood corona andextended corona of two graphs, Electron. J. Graph Theory Appl. 4 (1) (2016), 101--110.

J.A. Bondy and U.S.R. Murty, Graph Theory, Springer-Verlag, 2008.

L. Barriere, F. Comellas, C. Daflo, M. A. Fiol, The hierarchical product of graphs, Discrete Appl. Math. 157 (2009), 36--48.

L. Barriere, C. Daflo, M. A. Fiol, M. Mitjana, The generalized hierarchical product of graphs, Discrete Math. 309 (2009), 3871--3881.

H. Chen, N. Tzeng, Efficient resource placement in hypercubes using

multiple adjacency codes, III Trans. Comput. 43 (1994), 23--33.

H. Choo, S.-M. Yoo, H.Y. Youn, Processor scheduling and allocation

for 3D torus multicomputer systems, IEEE Trans. Parrallel Distrib.

Systems 11 (2000), 475--484.

M.V. Diudea, B. Parv, Molecular topology. 25. Hyper–Wiener index of dendrimers, MATCH Commun. Math. Comput. Chem. 32 (1995), 71--83.

R. Frucht, F. Harary, On the coronas of two graphs, Aequationes Math. 4 (1970), 322--324.

R. Hammack, W. Imrich, S. Klavzar, Handbook of Product Graphs, second ed., Taylor & Francis, Group, 2011.

S. Klavzar, S. Spacapan and J. Zerovnik, An almost complete description of perfect codes in direct product of cycles, Adv. in Appl. Math. 37 (2006), 2--18.

S. Klavzar, M. Tavakoli, Dominated and dominator colorings over (edge) corona and hierarchical products, Appl. Math. Comput. 390 (2021), 125647.

J. Kratochvil, Perfect codes over graphs, J. Combin. Theory Ser. B 40 (1986), 224--228.

M. Tavakoli, F. Rahbarnia and A. R. Ashrafi, Distribution of some graph invariants over Hierarchical Product of Graphs, Appl. Math. Comput. 220 (2013), 405--413.

M. Tavakoli, F. Rahbarnia, A. R. Ashrafi, Applications of generalized hierarchical product of graphs in computing the vertex and edge PI indices of chemical graphs, Ric. Mat. 63 (2014), 59--65.

M. Tavakoli, F. Rahbarnia and A.R. Ashrafi, Studying the corona oroduct of graphs under some graph invariants, Trans. Combin. 3 (2014), 43--49.

D.T. Taylor, Perfect r-codes in lexicographic products of graphs,

Ars Combin. 93 (2009), 215--223.

J. Vernold Vivin, K. Kaliraj, On equitable coloring of corona of wheels, Electron. J. Graph Theory Appl. 4 (2) (2016), 206--222.

Y.-N. Yeh and I. Gutman, On the sum of all distances in

composite graphs, Discrete Math. 135 (1994), 359--365.

J. Zerovnik, Perfect codes in direct products of cycles-a complete

characterization, Adv. in Appl. Math. 41 (2008), 197--205.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats