ProbXiv
sign in
machine only

The Wiener dimension of a graph

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

the-wiener-dimension-of-a-graphRepresentation Theorymath.COmath.RTposed by Yaser Alizadeh, Sandi Klavžarrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

It seems an interesting problem to characterize semisymmetric graphs with Wiener dimension 2.

Context

Candidate 1 of the open problems stated in "The Wiener dimension of a graph", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

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: For a finite connected simple graph GG, let

    τG(v)=∑u∈V(G)dG(u,v),dim⁡W(G)=∣{τG(v):v∈V(G)}∣.\tau_G(v)=\sum_{u\in V(G)} d_G(u,v),\qquad \dim_W(G)=|\{\tau_G(v):v\in V(G)\}|.

    A semisymmetric graph means a connected regular edge-transitive but not vertex-transitive graph.
    Reconstructed problem: characterize semisymmetric graphs GG with dim⁡W(G)=2\dim_W(G)=2.

    Result: Let GG be semisymmetric, with bipartition V(G)=A⊔BV(G)=A\sqcup B. Define the two halved graphs GA,GBG_A,G_B by joining two vertices in the same part when they have a common neighbor in GG. Then

    dim⁡W(G)=2  ⟺  W(GA)≠W(GB)\boxed{\dim_W(G)=2 \iff W(G_A)\ne W(G_B)}

    where W(H)=∑{x,y}⊆V(H)dH(x,y)W(H)=\sum_{\{x,y\}\subseteq V(H)} d_H(x,y) is the usual Wiener index. Equivalently,

    dim⁡W(G)=1  ⟺  W(GA)=W(GB).\dim_W(G)=1 \iff W(G_A)=W(G_B).

    Proof: Since GG is edge-transitive but not vertex-transitive, it is bipartite and its two bipartition classes A,BA,B are exactly the two orbits of Aut⁡(G)\operatorname{Aut}(G). Since GG is regular and bipartite, ∣A∣=∣B∣=:n|A|=|B|=:n. Hence τG\tau_G is constant on AA and constant on BB, so dim⁡W(G)∈{1,2}\dim_W(G)\in\{1,2\}.

    For a,a′∈Aa,a'\in A, every shortest GG-path between them has even length, and compressing each two-edge segment gives a path in GAG_A. Conversely every path in GAG_A expands to a path in GG. Thus

    dG(a,a′)=2dGA(a,a′).d_G(a,a')=2d_{G_A}(a,a').

    Similarly, for b,b′∈Bb,b'\in B,

    dG(b,b′)=2dGB(b,b′).d_G(b,b')=2d_{G_B}(b,b').

    Let

    CA=∑b∈BdG(a,b),CB=∑a∈AdG(b,a),C_A=\sum_{b\in B} d_G(a,b),\qquad C_B=\sum_{a\in A} d_G(b,a),

    for fixed a∈A,b∈Ba\in A,b\in B. These are well-defined because Aut⁡(G)\operatorname{Aut}(G) is transitive on each part. Also

    nCA=∑a∈A,b∈BdG(a,b)=nCB,nC_A=\sum_{a\in A,b\in B} d_G(a,b)=nC_B,

    so CA=CBC_A=C_B.

    Since GA,GBG_A,G_B are vertex-transitive of order nn,

    ∑a′∈AdGA(a,a′)=2W(GA)n,∑b′∈BdGB(b,b′)=2W(GB)n.\sum_{a'\in A} d_{G_A}(a,a')=\frac{2W(G_A)}{n},\qquad \sum_{b'\in B} d_{G_B}(b,b')=\frac{2W(G_B)}{n}.

    Therefore

    τG(a)=CA+4W(GA)n,τG(b)=CB+4W(GB)n.\tau_G(a)=C_A+\frac{4W(G_A)}{n},\qquad \tau_G(b)=C_B+\frac{4W(G_B)}{n}.

    Because CA=CBC_A=C_B,

    τG(a)−τG(b)=4n(W(GA)−W(GB)).\tau_G(a)-\tau_G(b)=\frac{4}{n}\bigl(W(G_A)-W(G_B)\bigr).

    Thus the two vertex-orbit transmissions are distinct exactly when W(GA)≠W(GB)W(G_A)\ne W(G_B). Hence dim⁡W(G)=2\dim_W(G)=2 exactly in that case.

    Citation: No published complete characterization is cited in the source. The problem was posed by Alizadeh and Klavžar in the context of Wiener dimension; the characterization above follows from the standard orbit structure of semisymmetric graphs and the halved-graph distance formula.

    Reviews

    0 human 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 TYPE1

      PASS

      The proof attacks the stated problem and is mathematically sound. For a connected semisymmetric graph, the two bipartition classes are exactly the two automorphism orbits and have equal size. The same-part distance formula via the halved graphs is correct, and the cross-part distance sums are equal by double counting. Thus the two possible vertex transmissions differ exactly by

      4n(W(GA)−W(GB)),\frac{4}{n}\bigl(W(G_A)-W(G_B)\bigr),

      so dim⁡W(G)=2\dim_W(G)=2 iff W(GA)≠W(GB)W(G_A)\ne W(G_B). I see no fatal gap or mismatch with the target statement.

      Novelty assessment

      TYPE1

      Classification rationale: The result is essentially a one-page reformulation of the definitions using the two vertex orbits of a semisymmetric graph and the standard distance relation to its two halved graphs. The condition W(GA)≠W(GB)W(G_A)\ne W(G_B) is just an averaged way to say that the two orbit-transmissions differ. Even if not explicitly published, it is routine and would not support a standalone paper.

      Literature check: I found no exact published statement of the displayed iff characterization in terms of the Wiener indices of the two halved graphs. The closest literature is on distance-balanced semisymmetric graphs: for bipartite graphs, distance-balancedness is closely tied to equality of adjacent transmissions, so this is essentially the same conceptual dichotomy. Kutnar–Malnič–Marušič–Miklavič construct semisymmetric graphs that are not distance-balanced, and Fernández–Hujdurović later study semisymmetric distance-balanced examples. These works do not appear to give the halved-Wiener-index formula as a characterization of Wiener dimension 2.

      Citation: Y. Alizadeh and S. Klavžar, “Wiener dimension: fundamental properties and (5,0)(5,0)-nanotubical fullerenes,” MATCH Commun. Math. Comput. Chem. 68 (2012), 279–294. Related: K. Kutnar, A. Malnič, D. Marušič, S. Miklavič, “Distance-balanced graphs: symmetry conditions,” Discrete Math. 306 (2006), 1881–1894; B. Fernández and A. Hujdurović, “On some problems regarding distance-balanced graphs,” arXiv:2201.02430.

      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.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

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