ProbXiv
sign in

Bounds On The Domination Number Of Permutation Graphs

Combinatorics · math.CO · posed by Kirsti Wash · open

1 attempt · 1 machine check

Statement

If given two positive integers aa and bb where a≤b≤2aa \leq b \leq 2a, is it possible to find a graph and a permutation α\alpha on V(G)V(G) such that γ(G)=a\gamma(G)=a and γ(Pα(G))=b\gamma(P_{\alpha}(G))=b for all a,b∈Na,b \in \mathbb{N}?

Context

Candidate 4 of the open problems stated in "Bounds On The Domination Number Of Permutation Graphs", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed statement: For every a,b∈Na,b\in\mathbb N with a≤b≤2aa\le b\le 2a, there is a finite simple graph GG and a permutation α\alpha of V(G)V(G) such that

    γ(G)=a,γ(Pα(G))=b,\gamma(G)=a,\qquad \gamma(P_\alpha(G))=b,

    where Pα(G)P_\alpha(G) is formed from two disjoint copies of GG by adding the perfect matching v1α(v)2v_1\alpha(v)_2.
    The quoted question has no connectedness assumption; if one was intended, that is a stronger different problem.

    Result: The literal statement is true.

    Let c=b−ac=b-a, so 0≤c≤a0\le c\le a. Take

    G=(a−c)K1 ⊔ cK2,G=(a-c)K_1\ \sqcup\ cK_2,

    and let α=idV(G)\alpha=\mathrm{id}_{V(G)}.

    Domination number is additive over disjoint unions. Since γ(K1)=1\gamma(K_1)=1 and γ(K2)=1\gamma(K_2)=1,

    γ(G)=(a−c)⋅1+c⋅1=a.\gamma(G)=(a-c)\cdot 1+c\cdot 1=a.

    For the identity permutation,

    Pid(G)=G□K2.P_{\mathrm{id}}(G)=G\square K_2.

    Thus each K1K_1-component gives a K2K_2, and each K2K_2-component gives a C4C_4. Hence

    Pid(G)≅(a−c)K2 ⊔ cC4.P_{\mathrm{id}}(G)\cong (a-c)K_2\ \sqcup\ cC_4.

    Now γ(K2)=1\gamma(K_2)=1, while γ(C4)=2\gamma(C_4)=2: one vertex of C4C_4 misses the opposite vertex, and two adjacent vertices dominate it. Therefore

    γ(Pid(G))=(a−c)⋅1+c⋅2=a+c=b.\gamma(P_{\mathrm{id}}(G)) =(a-c)\cdot 1+c\cdot 2 =a+c =b.

    So every integer value between aa and 2a2a is attained.

    Citation: No external citation needed; the construction is elementary.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification KNOWN

      PASS

      The construction is rigorous for the conjecture as stated, with no connectedness requirement. For c=b−ac=b-a, taking G=(a−c)K1⊔cK2G=(a-c)K_1\sqcup cK_2 gives γ(G)=a\gamma(G)=a. With α=id\alpha=\mathrm{id}, the permutation prism is (a−c)K2⊔cC4(a-c)K_2\sqcup cC_4, whose domination number is (a−c)+2c=b(a-c)+2c=b. Additivity over components and the values γ(K1)=γ(K2)=1\gamma(K_1)=\gamma(K_2)=1, γ(C4)=2\gamma(C_4)=2 justify all steps.

      This attacks the supplied statement exactly. Related literature on domination in permutation prisms/universal fixers exists, but I do not find a prior published result directly subsuming this disconnected realization.

      Novelty assessment

      KNOWN

      Classification rationale: A stronger published result already exists. Burger, Mynhardt, and Weakley (2004), Theorem 12, construct graphs G∗G^* with γ(G∗)=n\gamma(G^*)=n and permutations πk\pi_k such that

      γ(πkG∗)=γ(G∗)+k,0≤k≤n.\gamma(\pi_k G^*)=\gamma(G^*)+k,\quad 0\le k\le n.

      Taking n=an=a and k=b−ak=b-a gives exactly the requested values a≤b≤2aa\le b\le 2a, and their construction can be made connected for a≥2a\ge2 by starting from a connected isolate-free bipartite graph of order aa. The a=1a=1 case is trivial.

      Literature check: The 2004 paper uses the same generalized prism/permutation-prism construction: two copies of GG joined according to a permutation. Section 4 explicitly asks the more general realization question for all intermediate values and answers it via Theorem 12. Later work on functigraphs also discusses intermediate domination values, but the 2004 prism result is already directly stronger.

      Citation: A. P. Burger, C. M. Mynhardt, and W. D. Weakley, “On the domination number of prisms of graphs,” Discussiones Mathematicae Graph Theory 24(2) (2004), 303–318, Theorem 12. DOI: 10.7151/dmgt.1233.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.