Invariants of E-graphs

Abstract

An E-graph is constructed by replacing each edge in a core graph G with a copy of a graph H. An important property of E-graphs is that their invariant values can be determined from parameters of the original graphs G and H. We determine chromatic number, clique number, vertex and edge cover numbers, vertex and edge independence numbers, circumference, and girth of E-graphs. A characterization of hamiltonian E-graphs is also given.

Keywords:

• E-graphs chromatic number
• clique number
• girth
• circumference
• vertex and edge independence numbers
• vertex and edge cover numbers