Download PDF - The edge C₄ graph of some graph classesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

The edge C₄ graph of some graph classes

Authors 1, 1

Affiliations

  1. Department of Mathematics, Cochin University of Science and Technology, Cochin-682022, India

Abstract

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(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(E₄(H)) = E₄(G). Also we give forbidden subgraph characterizations for E₄(G) being a threshold graph, block graph, geodetic graph and weakly geodetic graph.

Keywords

ENG
edge C₄ graph, threshold graph, block graph, geodetic graph, weakly geodetic graph

Bibliography

  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 C₄ 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).
Discussiones Mathematicae Graph Theory
2010/30/3
Export to PBN, Opens in new tab
Pages:
365-375
Main language of publication
English
Received
2008-09-05
Accepted
2009-03-26
Published
2010

DOI: 10.7151/dmgt.1499

Exact and natural sciences