Graph Parameters and Functional Relations
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
This submission defines five parameters of finite simple undirected graphs: maximum matching number, twin-cover number, neighborhood diversity, degeneracy, and arboricity. Disconnected graphs are included, and all five parameters assign value zero to the empty graph.
The parameters are defined through matchings, twin-covers, neighborhood partitions, degree conditions on induced subgraphs, and partitions of the edge set into forests, respectively. Each parameter has its own definition concept.
Five further definitions express functional boundedness, functional equivalence, absence of a functional bound, strict functional boundedness, and incomparability on all finite simple graphs. A theorem, with a Lean proof, identifies mutual nondecreasing functional bounds with the existing Lax notion of functional equivalence. No comparisons between the five concrete parameters are asserted.
A second theorem establishes that exactly one of four relations holds for every parameter pair: strict functional boundedness in either direction, functional equivalence, or incomparability.
A third theorem proves that functional equivalence is an equivalence relation. A fourth proves that strict functional boundedness is a strict partial order. A fifth proves that incomparability is symmetric and irreflexive.
Concepts
- thm✓
EquivalentEquivalence - thm✓
FunctionalEquivalenceConnection - thm✓
IncomparableProperties - thm✓
RelationClassification - thm✓
StrictlyBoundsOrder
- def
Arboricity - def
Bounds - def
Degeneracy - def
DoesNotBound - def
Equivalent - def
Incomparable - def
MaximumMatching - def
NeighborhoodDiversity - def
StrictlyBounds - def
TwinCover
Concept map
Proofs
Proof networkview on GitHub
Proof list
-
⊢
Lax825442Proofs.EquivalentEquivalence.equivalent_equivalence -
⊢
Lax825442Proofs.FunctionalEquivalenceConnection.functionallyEquivalent_iff -
⊢
Lax825442Proofs.IncomparableProperties.incomparable_symmetric_irreflexive -
⊢
Lax825442Proofs.RelationClassification.relationClassification -
⊢
Lax825442Proofs.StrictlyBoundsOrder.strictlyBounds_strictOrder
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
Cite this
This is only the formalizers. The authors of the formalized results may be different (see References).
@misc{lax-825442,
title = {Graph Parameters and Functional Relations},
year = {2026},
howpublished = {Lax Archive, lax-825442},
url = {https://laxarchive.org/lax-825442/},
note = {draft},
}
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments