Geodesic
Properties of Hereditary Hypergraphs and Middle Graphs
Canadian mathematical bulletin, Tome 21 (1978) no. 4, pp. 461-468

Voir la notice de l'article provenant de la source Cambridge University Press

The middle graph of a graph G=( V, E) is the graph M(G) = (V∪E, E′), in which two vertices u, v are adjacent if either M is a vertex in V and v is an edge in E containing u, or u and v are edges in E having a vertex in common. Middle graphs have been characterized in terms of line graphs by Hamada and Yoshimura [7], who also investigated their traversability and connectivity properties. In this paper another characterization of middle graphs is presented, in which they are viewed as a class of intersection (representative) graphs of hereditary hypergraphs. Graph theoretic parameters associated with the concepts of vertex independence, dominance, and irredundance for middle graphs are discussed, and equalities relating the chromatic number of a graph to these parameters are obtained. 
Cockayne, E. J.; Hedetniemi, S. T.; Miller, D. J. Properties of Hereditary Hypergraphs and Middle Graphs. Canadian mathematical bulletin, Tome 21 (1978) no. 4, pp. 461-468. doi: 10.4153/CMB-1978-079-5
@article{10_4153_CMB_1978_079_5,
     author = {Cockayne, E. J. and Hedetniemi, S. T. and Miller, D. J.},
     title = {Properties of {Hereditary} {Hypergraphs} and {Middle} {Graphs}},
     journal = {Canadian mathematical bulletin},
     pages = {461--468},
     year = {1978},
     volume = {21},
     number = {4},
     doi = {10.4153/CMB-1978-079-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1978-079-5/}
}
TY  - JOUR
AU  - Cockayne, E. J.
AU  - Hedetniemi, S. T.
AU  - Miller, D. J.
TI  - Properties of Hereditary Hypergraphs and Middle Graphs
JO  - Canadian mathematical bulletin
PY  - 1978
SP  - 461
EP  - 468
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1978-079-5/
DO  - 10.4153/CMB-1978-079-5
ID  - 10_4153_CMB_1978_079_5
ER  - 
%0 Journal Article
%A Cockayne, E. J.
%A Hedetniemi, S. T.
%A Miller, D. J.
%T Properties of Hereditary Hypergraphs and Middle Graphs
%J Canadian mathematical bulletin
%D 1978
%P 461-468
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1978-079-5/
%R 10.4153/CMB-1978-079-5
%F 10_4153_CMB_1978_079_5

[1] 1. Berge, C., Graphs and Hypergraphs, American Elsevier Inc., New York, 1973. Google Scholar

[2] 2. Cockayne, E. J. and Hedetniemi, S. T., Independence Graphs, Proc. 5th S.E. Conf. on Combinatorics, Graph Theory and Computing (1974), 471-491. Google Scholar

[3] 3. Cockayne, E. J. and Hedetniemi, S. T., Optimal Domination in Graphs, IEEE Trans, on Circuits and Systems Vol. CAS-22 No. 11 (1975), 855-857. Google Scholar

[4] 4. Cockayne, E. J. and Hedetniemi, S. T., Towards a Theory of Domination in Graphs, Networks 7 (1977), 247-261. Google Scholar

[5] 5. Cockayne, E. J. and Hedetniemi, S. T., Disjoint Independent Dominating Sets in Graphs, Discrete Math. 15 (1976), 213-222. Google Scholar

[6] 6. Gallai, T., Ûber extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2 (1959), 133-138. Google Scholar

[7] 7. Gallai, T. and Yoshimura, I., Traversability and Connectivity of the Middle Graph of a Graph, Discrete Math. 14 (1976), 247-255. Google Scholar

[8] 8. Kônig, D., Graphen und Matrizen, Mat. Fiz. Lapok 38 (1931), 116-119. Google Scholar

[9] 9. Krausz, J., Démonstration nouvelle d'un théorème de Whitney sur les réseaux, Mat. Fiz. Lapok 50 (1943), 75-89. Google Scholar

[10] 10. Ore, O., Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38, Providence, 1962. Google Scholar

[11] 11. Sabidussi, G., Graph Derivatives, Math. Z. 76 (1961), 385-401. Google Scholar

[12] 12. Sampathkumar, E. and Chikkodimath, S. B., Semi-Total Graphs of a Graph-I, Karnatak Univ. Journal: Science-Vol. XVffl, 1973. Google Scholar

[13] 13. Slater, P. J., Irreducible Point Independence Numbers and Independence Graphs, Proc. 5th S.E. Conf. on Combinatorics, Graph Theory and Computing (1974), 647-660. Google Scholar

[14] 14. Vizing, V. G., On an Estimate of the Chromatic Class of a p-graph, Diskret. Analiz. 3 (1964), 25-30. Google Scholar

[15] 15. Whitney, H., Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), 150-168. Google Scholar

Cité par Sources :