The edge C₄ graph of some graph classes

Manju K. Menon; A. Vijayakumar

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 3, page 365-375
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Manju K. Menon, and A. Vijayakumar. "The edge C₄ graph of some graph classes." Discussiones Mathematicae Graph Theory 30.3 (2010): 365-375. <http://eudml.org/doc/270807>.

@article{ManjuK2010,
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.},
author = {Manju K. Menon, A. Vijayakumar},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge C₄ graph; threshold graph; block graph; geodetic graph; weakly geodetic graph; edge graph},
language = {eng},
number = {3},
pages = {365-375},
title = {The edge C₄ graph of some graph classes},
url = {http://eudml.org/doc/270807},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Manju K. Menon
AU - A. Vijayakumar
TI - The edge C₄ graph of some graph classes
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 3
SP - 365
EP - 375
AB - 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.
LA - eng
KW - edge C₄ graph; threshold graph; block graph; geodetic graph; weakly geodetic graph; edge graph
UR - http://eudml.org/doc/270807
ER -

References

top
  1. [1] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes (SIAM, 1999). Zbl0919.05001
  2. [2] V. Chvátal and P.L. Hammer, Aggregation of inequalities in integer programming, Ann. Discrete Math. 1 (1997) 145-162. 
  3. [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. Zbl0575.68065
  4. [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. Zbl0389.05048
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1988). Zbl0890.05002
  6. [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. Zbl0337.05138
  7. [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. Zbl0139.17301
  8. [8] M. Knor, L. Niepel and L. Soltes, Centers in line graphs, Math. Slovaca 43 (1993) 11-20. 
  9. [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. Zbl1202.05116
  10. [10] O. Ore, Theory of Graphs, Amer. Math. Soc. Coll. Publ. 38, (Providence R.I, 1962). 
  11. [11] E. Prisner, Graph Dynamics (Longman, 1995). Zbl0848.05001
  12. [12] S.B. Rao, A. Lakshmanan and A. Vijayakumar, Cographic and global cographic domination number of a graph, Ars Combin. (to appear). Zbl1249.05295
  13. [13] D.B. West, Introduction to Graph Theory (Prentice Hall of India, 2003). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.