Possibilities for the graph center

Task number: 4235

Find out which graphs can be the center of another graph. Thus, for which graphs \( H \) there exists a graph \( G \) such that when \( C \) is a set of vertices that belong to the center of \( G \), then the induced subgraph of \( G \) on the set \( C \) is isomorphic to \( H \)?

The center of the general graph is, similarly to the tree, formed by vertices with minimal eccentricity.

  • Solution

    If \( H \) is complete, just take \( G = H \).

    Otherwise, we add two new edges \( (u, v) \) and \( (u ’, v’) \) to \( H \) and connect vertices \( u \) and \( u ’\) to all vertices of \( H \). The resulting graph \( G \) contains \( H \) as an induced subgraph.

    The vertices of \( H \) have eccentricity 2, the vertices \( u \) and \( u’\) have eccentricity 3, and the vertices \( v \) and \( v’\) have eccentricity of 4.

  • Answer

    Any non-empty graph can form the center of a graph.

Difficulty level: Moderate task
Solution require uncommon idea
Cs translation
Send comment on task by email