Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-18T12:59:49.506Z Has data issue: false hasContentIssue false
  • English
  • Français

Properties of Hereditary Hypergraphs and Middle Graphs

Published online by Cambridge University Press:  20 November 2018

E. J. Cockayne ,
S. T. Hedetniemi  and
D. J. Miller
E. J. Cockayne
Affiliation:
Department of Mathematics, University of Victoria, Victoria, B.C. V8W 2Y2
S. T. Hedetniemi
Affiliation:
Department of Mathematics, University of Victoria, Victoria, B.C. V8W 2Y2
D. J. Miller
Affiliation:
Department of Mathematics, University of Victoria, Victoria, B.C. V8W 2Y2
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 21 , Issue 4 , 01 December 1978 , pp. 461 - 468
Copyright
Copyright © Canadian Mathematical Society 1978

References

1. Berge, C., Graphs and Hypergraphs, American Elsevier Inc., New York, 1973.Google Scholar
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. 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. Cockayne, E. J. and Hedetniemi, S. T., Towards a Theory of Domination in Graphs, Networks 7 (1977), 247-261.Google Scholar
5. Cockayne, E. J. and Hedetniemi, S. T., Disjoint Independent Dominating Sets in Graphs, Discrete Math. 15 (1976), 213-222.Google Scholar
6. Gallai, T., Ûber extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2 (1959), 133-138.Google Scholar
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. Kônig, D., Graphen und Matrizen, Mat. Fiz. Lapok 38 (1931), 116-119.Google Scholar
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. Ore, O., Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38, Providence, 1962.Google Scholar
11. Sabidussi, G., Graph Derivatives, Math. Z. 76 (1961), 385-401.Google Scholar
12. Sampathkumar, E. and Chikkodimath, S. B., Semi-Total Graphs of a Graph-I, Karnatak Univ. Journal: Science-Vol. XVffl, 1973.Google Scholar
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. Vizing, V. G., On an Estimate of the Chromatic Class of a p-graph, Diskret. Analiz. 3 (1964), 25-30.Google Scholar
15. Whitney, H., Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), 150-168.Google Scholar