Graph invariants and labelings

Numerical and polynomial invariants of graphs such as degree sequences, arboricity, induced forest number, Shannon capacity and the chromatic symmetric function, and graph labelings.

• Chromatic symmetric function
• Edge-graceful labelings
• Induced forest number
• Nash-Williams arboricity theorem
• Prime labelings of ladder graphs
• Shannon capacity of a graph

TheoremErdős–Gallai theorem#✓fully proved

Let \(V\) be a finite set and \(d \colon V \to \mathbb{N}\). There is a simple graph on \(V\) in which every vertex \(v\) has degree \(d(v)\) if and only if the sum \(\sum_{v \in V} d(v)\) is even and, for every subset \(S \subseteq V\),

\[\sum_{v \in S} d(v) \le |S|(|S| - 1) + \sum_{v \in V \setminus S} \min(d(v), |S|).\]

theorem erdos_gallai {V : Type*} [Fintype V] [DecidableEq V]
    (d : V → ℕ) :
    (∃ G : SimpleGraph V, ∃ _ : DecidableRel G.Adj, ∀ v, G.degree v = d v) ↔
      Even (∑ v : V, d v) ∧
        ∀ S : Finset V,
          ∑ v ∈ S, d v ≤ S.card * (S.card - 1) +
            ∑ v ∈ Finset.univ \ S, min (d v) S.card

Sources

• P. Erdős and T. Gallai, Graphs with prescribed degrees of vertices, Matematikai Lapok 11 (1960), 264-274.

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.