Twin-cover number

Lax825442.TwinCover · concepts/Lax825442/TwinCover.lean · lax-825442

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    Two adjacent vertices are true twins if they have the same neighbors outside the pair. A twin-cover is a set of vertices that meets every edge whose endpoints are not true twins in the original graph. The twin-cover number is the minimum size of a twin-cover.

    Concept map
    1 concept
    100%
    DefinitionThis concept

    Lean source view on GitHub

    1import Mathlib.Combinatorics.SimpleGraph.Finite
    2import Mathlib.Data.Set.Card
    3import Mathlib.Order.Lattice.Nat
    4
    5/-!
    6---
    7title: Twin-cover number
    8type: definition
    9---
    10Two adjacent vertices are true twins if they have the same neighbors outside
    11the pair. A twin-cover is a set of vertices that meets every edge whose
    12endpoints are not true twins in the original graph. The twin-cover number is
    13the minimum size of a twin-cover.
    14-/
    15
    16namespace Lax825442.TwinCover
    17
    18/-- Adjacent vertices with the same neighbors outside the pair. -/
    19def TrueTwins {V : Type} (G : SimpleGraph V) (u v : V) : Prop :=
    20 G.Adj u v ∧ (∀ w : V,
    21 (w ≠ u ∧ w ≠ v) → (G.Adj u w ↔ G.Adj v w))
    22
    23/-- A set meeting every edge except those between true twins. -/
    24def IsTwinCover {V : Type} (G : SimpleGraph V) (S : Set V) : Prop :=
    25 ∀ ⦃u v : V⦄,
    26 (G.Adj u v ∧ ¬ TrueTwins G u v) → (u ∈ S ∨ v ∈ S)
    27
    28/-- The minimum cardinality of a twin-cover. -/
    29noncomputable def twinCover {V : Type} [Fintype V] [DecidableEq V]
    30 (G : SimpleGraph V) : ℕ :=
    31 sInf {k | ∃ S : Set V, (S.ncard = k) ∧ IsTwinCover G S}
    32
    33end Lax825442.TwinCover
    34

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…