Discussiones Mathematicae Graph Theory 30(3) (2010) 365-375
doi: 10.7151/dmgt.1499

[BIBTex] [PDF] [PS]


Manju K. Menon  and  A. Vijayakumar

Department of Mathematics
Cochin University of Science and Technology
Cochin-682022, India
e-mail: manjumenonk@gmail.com
e-mail: vijay@cusat.ac.in


The edge C4 graph of a graph G, E4(G) is a graph whose vertices are the edges of G and two vertices in E4(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C4. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C4 graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E4(G). It is shown that for any graph G without isolated vertices, there exists a super graph H such that C(H) = G and C(E4(H)) = E4(G). Also we give forbidden subgraph characterizations for E4(G) being a threshold graph, block graph, geodetic graph and weakly geodetic graph.

Keywords: edge C4 graph, threshold graph, block graph, geodetic graph, weakly geodetic graph.

2010 Mathematics Subject Classification: 05C99.


[1] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes (SIAM, 1999).
[2] V. Chvátal and P.L. Hammer, Aggregation of inequalities in integer programming, Ann. Discrete Math. 1 (1997) 145-162.
[3] D.G. Corneil, Y. Perl and I.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985) 926-934, doi: 10.1137/0214065.
[4] S. Foldes and P.L. Hammer, The Dilworth number of a graph, Ann. Discrete Math. 2 (1978) 211-219, doi: 10.1016/S0167-5060(08)70334-0.
[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1988).
[6] E. Howorka, On metric properties of certain clique graphs, J. Combin. Theory (B) 27 (1979) 67-74, doi: 10.1016/0095-8956(79)90069-8.
[7] D.C. Kay and G. Chartrand, A characterization of certain Ptolemic graphs, Canad. J. Math. 17 (1965) 342-346, doi: 10.4153/CJM-1965-034-0.
[8] M. Knor, L. Niepel and L. Soltes, Centers in line graphs, Math. Slovaca 43 (1993) 11-20.
[9] M.K. Menon and A. Vijayakumar, The edge C4 graph of a graph, in: Proc. International Conference on Discrete Math. Ramanujan Math. Soc. Lect. Notes Ser. 7 (2008) 245-248.
[10] O. Ore, Theory of Graphs, Amer. Math. Soc. Coll. Publ. 38, (Providence R.I, 1962).
[11] E. Prisner, Graph Dynamics (Longman, 1995).
[12] S.B. Rao, A. Lakshmanan and A. Vijayakumar, Cographic and global cographic domination number of a graph, Ars Combin. (to appear).
[13] D.B. West, Introduction to Graph Theory (Prentice Hall of India, 2003).

Received 5 September 2008
Revised 26 March 2009
Accepted 16 July 2009