On Common Neighborhood Graphs II

Document Type : Research Paper


1 Tarbiat Modares University

2 University of Kragujevac


Let G be a simple graph with vertex set V (G). The common neighborhood graph or congraph of G, denoted by con(G), is a graph with vertex set V (G), in which two vertices are adjacent if and only if they have at least one common neighbor in G. We compute the congraphs of some composite graphs. Using these results, the congraphs of several special graphs are determined.


Main Subjects

1. A. Alwardi, B. Arsić, I. Gutman, N. D. Soner, The common neighborhood graph and its
energy, Iranian J. Math. Sci. Inform. 7 (2012) 1–8.
2. A. Alwardi, N. D. Soner, I. Gutman, On the common–neighborhood energy of a graph,
Bull. Acad. Serbe Sci. Arts (Cl. Sci. Math. Natur.) 143 (2011) 49–59.
3. S. K. Ayyaswamy, S. Balachandran, I. Gutman, On second–stage spectrum and energy
of a graph, Kragujevac J. Math. 34 (2010) 139–146.
4. S. K. Ayyaswamy, S. Balachandran, K. Kannan, Bounds on the second stage spectral
radius of graphs, Int. J. Math. Sci. 1 (2009) 223–226.
5. J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, New York, 2008.
6. A. S. Bonifácio, R. R. Rosa, I. Gutman, N. M. M. de Abreu, Complete common
neighborhood graphs, Proc. Congreso Latino–Iberoamericano de Investigación
Operativa & Simpósio Brasileiro de Pesquisa Operacional (2012) 4026–4032.
7. M. Caramia, P. Del l Olmo, A lower bound on the chromatic number of Mycielski
graphs, Discrete Math. 235 (2001) 79–86.
8. V. Chvátal, The minimality of the Mycielski graph, Lecture Notes Math. 406 (1974)
9. K. L. Collins, K. Tysdal, Dependent edges in Mycielski graphs and 4-colorings of 4-
skeletons, J. Graph Theory 46 (2004) 285–296.
10. T. Došlić, Splices, links, and their degree-weighted Wiener polynomials, Graph Theory
Notes New York 48 (2005) 47–55.
11. G. Hajós, Über eine Konstruktion nicht n -färbbarer Graphen, Wiss. Z. Martin Luther
Univ. 10 (1961) 116–117.
12. S. Hossein–Zadeh, A. Iranmanesh, A. Hamzeh, M. A. Hosseinzadeh, On the common
neighborhood graphs, El. Notes Discr. Math. 45 (2014) 51–56.
13. Y. Hou, W. C. Shiu, The spectrum of the edge corona of two graphs, El. J. Lin. Algebra
20 (2010) 586–594.
14. W. Imrich, S. Klavžar, Product of Graphs – Structure and Recognition, Wiley, New
York, 2000.
15. M. Knor, B. Lužar, R. Škrekovski, I. Gutman, On Wiener index of common
neighborhood graphs, MATCH Commun. Math. Comput. Chem. 72 (2014) 321–332.
16. J. Mycielski, Sur le colouriage des graphes, Colloq. Math. 3 (1955) 161-162.
17. J. Vernold Vivin, Harmonious coloring of total graphs, n -leaf, central graphs and
circumdetic graphs, Ph. D. Thesis, Bharathiar Univ., Coimbatore, India, 2007.
18. J. Vernold Vivin, M. M. Akbar Ali, K. Thilagavathi, Harmonious coloring on central
graphs of odd cycles and complete graphs, Proc. Int. Conf. Math. Comput. Sci., Loyola
College, Chennai, India, 1−3 (2007) 74–78.
19. J. Vernold Vivin, M. M. Akbar Ali, K. Thilagavathi, On Harmonious coloring of
central graphs, Adv. Appl. Discr. Math. 2 (2008) 17−33.