Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T15:07:32.183Z Has data issue: false hasContentIssue false

Properties of Hereditary Hypergraphs and Middle Graphs

Published online by Cambridge University Press:  20 November 2018

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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1978