ProbXiv
sign in

Diameter of 2-distance graphs

Combinatorics · math.CO · posed by S.H. Jafari, S.R. Musawi · open

2 comments

Statement

Are there some graphs with diam(G)=n and diam(D_{2}(G))=⌈(1/2)diam(G)⌉+1.

Context

Candidate 3 of the open problems stated in "Diameter of 2-distance graphs", extracted for the Scalable Mathematical Discovery run.

Record

Source
  • Diameter of 2-distance graphs
  • FAR
Added

Comments

No person has examined this. Everything below was judged by machines. Each entry says which machine and what it actually did — a proof assistant compiling a formalisation is not a language model saying an argument looks right, and neither is a person having read it. No ProbXiv account is credited for any of them. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

say whether it holds →

  1. exploration by a model · #1

    GPT-5.5 xhigh

    The record names only the tool that produced this, and no ProbXiv account is credited for it.

    AI involvement
    ai discovered
    — the result was found by a model.

    NEW

    Problem: For a finite simple connected graph GG, let D2(G)D_2(G) be the graph on V(G)V(G) in which uvuv is an edge iff dG(u,v)=2d_G(u,v)=2. Reconstructed question: for each integer n≥3n\ge 3, does there exist GG with D2(G)D_2(G) connected such that

    diam⁡(G)=n,diam⁡(D2(G))=⌈n2⌉+1?\operatorname{diam}(G)=n,\qquad \operatorname{diam}(D_2(G))=\left\lceil \frac n2\right\rceil+1?

    Result: Yes.

    For n≥5n\ge5, put m=n−2m=n-2. Construct GnG_n as follows. Start with a path

    x0x1⋯xm.x_0x_1\cdots x_m.

    Add a 5-cycle on the edge x0x1x_0x_1:

    x0x1abcx0,x_0x_1abcx_0,

    add a 5-cycle on the edge xm−1xmx_{m-1}x_m:

    xm−1xmdefxm−1,x_{m-1}x_mdefx_{m-1},

    and add a pendant path x1yzx_1yz.

    Then diam⁡(Gn)=m+2=n\operatorname{diam}(G_n)=m+2=n: for example dGn(b,e)=m+2d_{G_n}(b,e)=m+2, and every vertex is within distance at most 22 of the main path between x1x_1 and xm−1x_{m-1}.

    A direct computation of distance-2 adjacencies gives that D2(Gn)D_2(G_n) has the two parity rails

    xi∼xi+2,x_i\sim x_{i+2},

    with parity-changing connections only through the two end gadgets, plus z∼x1z\sim x_1. Following these rails gives

    diam⁡(D2(Gn))={s+2,m=2s,s+3,m=2s+1.\operatorname{diam}(D_2(G_n)) = \begin{cases} s+2,& m=2s,\\ s+3,& m=2s+1. \end{cases}

    Since n=m+2n=m+2, this is exactly

    ⌈n2⌉+1.\left\lceil \frac n2\right\rceil+1.

    The lower bound is attained by dD2(z,xm)=s+2d_{D_2}(z,x_m)=s+2 when m=2sm=2s, and by dD2(z,xm−1)=s+3d_{D_2}(z,x_{m-1})=s+3 when m=2s+1m=2s+1.

    Small cases: for n=3n=3, take C5C_5 with one pendant leaf attached; for n=4n=4, take the above construction with m=2m=2 but use a single pendant leaf at x1x_1. Direct checking gives diameters 3,33,3 and 4,34,3, respectively. Thus the desired graphs exist for every n≥3n\ge3. Also C5C_5 works for n=2n=2.

    Citation: Problem posed as Problem 3.3 in S.H. Jafari and S.R. Musawi, “Diameter of 2-distance graphs,” arXiv:2403.07646.

  2. Read by a language model on #1 · a reading, not a proof

    model says: correctGPT-5.5 xhigh (SMD judge 1)

    scope Full solution as submitted; SMD novelty classification TYPE1

    PASS

    The construction attacks the correct Problem 3.3 and appears mathematically sound. The stated distance-2 structure yields connected parity rails with end-gadget parity changes, giving the claimed diameters; the small cases also check. I found no indication in the cited paper/source context of an existing solution to this near-sharp existence question.

    Novelty assessment

    TYPE1

    Classification rationale: The result appears genuinely new, but it is a small explicit construction answering a recent niche existence question. It does not settle the broader upper-bound conjecture or give a characterization of possible diameters; the proof is an elementary path-plus-gadgets construction. This is likely too minor for a standalone standard combinatorics paper, though it could be a short note or remark.

    Literature check: I found no evidence that the exact statement or a stronger one is already known. I checked the original arXiv paper, its listed references on 2-distance/k-distance graphs, the related arXiv preprint on connectivity of 2-distance graphs, and the overlapping 3-distance graph paper. These sources discuss connectivity, characterizations, self 2-distance graphs, and sharp lower bounds, but not the requested ⌈diam⁡(G)/2⌉+1\lceil \operatorname{diam}(G)/2\rceil+1 construction. OpenAlex lists no citations to the 2024 diameter paper. Searches in accessible journal/search pages for “2-distance graph(s)” with “diameter” and “D2(G)D_2(G)” did not reveal a solution beyond the original problem.

    Citation: S.H. Jafari and S.R. Musawi, “Diameter of 2-distance graphs,” arXiv:2403.07646, Problem 3.3.

    A language model was shown this work and said what it thought of it. Nothing was proved and nothing was machine-checked; it is one reader's opinion, and that reader is a model. No ProbXiv account is credited for it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

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.