0
$\begingroup$

For a simple graph $G$, the $\text{average-degree}(G)=|E(G)|/|V(G)|$ and
the maximum average degree $\text{mad}(G)=\max\{\text{average-degree}(H)\colon H \text{ is a subgraph of } G\}$.

If $\text{average-degree}(G)=\text{mad}(G)$, what can we say about the structure of $G$?

Clearly, $\text{average-degree}(G)=\text{mad}(G)$ for every regular graph $G$. I suppose the graph being regular is not a necessary condition.

Context: Both parameters are equal for extremal graphs in some graph coloring problems.

$\endgroup$
1
  • $\begingroup$ Isn't this class of bounded arboricity graphs? Or similarly class of bounded degeneracy graphs? $\endgroup$
    – Saeed
    Feb 25 at 6:55

1 Answer 1

1
$\begingroup$

This question is a bit open-ended, but here are some observations:

Some non-regular graphs can have this property, for example all trees have this property.

For graph coloring, this property seems to have limited use. In particular, there is a reduction from any graph $G$ to a graph $G'$ that satisfies this property and $\chi(G') = \chi(G)+1$, where $\chi(G)$ denotes the chromatic number of $G$. The reduction is as follows:

Denote $n = |V(G)|$. Construct $G'$ by adding $n$ new vertices, each connected to every vertex of $V(G)$ but not to each other. Now, $\chi(G') = \chi(G)+1$ because the new vertices need an additional color but only one additional color suffices. I claim that $G'$ has the average degree property. Let $G'[X]$ be the induced subgraph of $G'$ with the highest average degree. I claim that $G'[X] = G'$. Let $A$ denote the original vertices $V(G)$ and $B$ denote the added vertices. Now, the average degree of $G'[X]$ is strictly less than $|A \cap X|$, because each vertex in $B \cap X$ contributes $|A \cap X|$ edges, and after counting edges adjacent to $B \cap X$, the vertices in $A \cap X$ contribute strictly less than $|A \cap X|$ edges. Now, if $X \cap B \neq B$, we could add a vertex in $B$ to $X$, contributing $|A \cap X|$ new edges, and therefore increasing average-degree. Therefore $X$ must contain $B$. Suppose $X \cap A \neq A$. Now, as $B \subseteq X$, adding a vertex of $A$ to $X$ contributes at least $|B| > |A \cap X|$ new edges, and therefore increases the average degree. Therefore $X$ must contain both $A$ and $B$, so $G'[X] = G'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.