Meaning of term "characterization" in graph theory

Question

I am working on self-centered graphs. And in a project, I have been asked to characterize self-centered graphs? What basically I have to write about that? I am confused by the term "Characterization" in graph theory. Can someone explain it briefly what does it mean?

Answer 1

This is a good question, and it doesn't seem like you were satisfied by the previous answer. Unfortunately, "characterizing" a class of graphs can mean a lot of different things. Some classes admit very clean characterizations; for instance, bipartite graphs are exactly those graphs in which $V(G)$ admits a partition into 2 independent sets (I would call this a vertex-partition characterization), and the class of split graphs are exactly those which are ($2K_2$, $C_4$, $C_5$)-free (I'd call this a forbidden subgraph characterization). In essence, a characterization is somehow the simplest way you could describe your class of graphs to someone, without using the name of your class. Perhaps the best way is to explain the concept is to simply give you a small list of ways to characterize graphs:

• Forbidden subgraphs/structures: This is a characterization by giving some finite list of subgraphs/structures which, if avoided, give a graph in your class. Split graphs were given as an example above, and another is perfect graphs (which are (odd-hole, odd anti-hole)-free).

• Vertex orderings: This is a characterization which says that a graph $G$ is a member of some class if and only if $V(G)$ has an ordering satisfying some specific property. For instance, chordal graphs are exactly those which admit a so-called "perfect elimination ordering."

• Representations/Intersections: This is a characterization which says that a graph is a member of some class if and only if it may be "represented" as a model, usually in terms of intersection. For instance, interval graphs are exactly the graphs whose vertices may be represented as intervals of the real line, where adjacencies are encoded by whether two intervals (vertices) have nontrivial intersection.

• Orientations: This is a characterization which says that a graph is a member of some class if and only if there is an orientation of the graph (i.e. an imposition of direction to each edge, changing them to arcs) satisfying some property. For instance, comparability graphs are exactly those which are transitively orientable.

• Vertex partitions: This is a characterization which says that a graph $G$ is a member of some class if and only if $V(G)$ may be partitioned in a way satisfying certain properties. The example of bipartite graphs were given above, and others include polar graphs (those in which $V(G)$ may be partitioned into sets $A$ and $B$ such that the connected components of $\overline{G[A]}$ and $G[B]$ are both cliques), and threshold-tolerance graphs (which are exactly those which admit a so-called "blue-red partition").

For reference, the site https://www.graphclasses.org/ is quite useful for this matter; especially for the characterizations by forbidden subgraphs. To get started, search up your favorite class of graphs, and (provided that they are well-studied and sufficiently "nice") there should be an equivalent characterization by forbidden subgraphs under the "Equivalent classes" heading. For example, when I search comparability graphs, we see that they are equivalently characterized by a list of 18 forbidden subgraphs (some of which are infinite families!).

Hopefully this helps.

Answer 2

Completely describe the class of self-centerd graph, i.e., give a kind of list (or other parametric construction or something like that) such that every self-centered graph is isomorphic to exactly one of the graphs in your list.