Distinguishing Number of Non-Zero Component Graphs

H. Benish; I. Javaid; M. Murtaza

REVIEW 5 major objections 6 minor 17 references

Distinguishing Number of Non-Zero Component Graphs

T0 review · 5 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims the automorphism group of a nonzero component graph is the symmetric group on the basis and derives distinguishing numbers, but the automorphism claim fails for q≥3 and the q=2 proof has a gap.

desk verdict The paper's central isomorphism claim is false for q≥3, and the q=2 distinguishing proof has real gaps; the salvageable kernel is small. read the letter →

arxiv 1908.01001 v1 pith:MENFMDQ5 submitted 2019-08-01 math.CO

I. Javaid , M. Murtaza , H. Benish This is my paper · ORCID

classification math.CO

keywords mathbbnon-zerovectorscomponentbasisgraphnumberautomorphism

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

A non-zero component graph is built from a finite vector space. Each non-zero vector is a vertex, and two vertices are connected when the two vectors share at least one basis vector with a non-zero coefficient. For binary fields (two elements), each non-zero vector is just a non-empty set of basis vectors, and two sets are adjacent when they intersect.

The authors prove that every permutation of the basis extends to a graph automorphism, and then claim the graph's full automorphism group is exactly that symmetric group. This is true only for the binary field. Over larger fields, automorphisms can also scale individual basis vectors independently, so the automorphism group is much larger. For example, over a three-element field, the map that sends the first coordinate to twice itself is a non-trivial automorphism that moves a basis vector to a non-basis vector, and it is not induced by any permutation of the chosen basis. The paper's Corollary 2.10, which asserts every automorphism restricts to a permutation of the chosen basis, is therefore false over larger fields.

The distinguishing-number results are: for binary fields they claim two colors suffice; for larger fields they claim (q-1)^n colors are necessary and sufficient. The lower bound from twin sets is sound. But the proof that two colors suffice contains an explicit set-membership error: the vertices assigned label 1 in class T_{n-1} are written with skeletons of the wrong size, so the construction does not actually use vertices from that class. The logic of Lemma 3.1 also does not guarantee that the displayed non-adjacent pair is mapped by the transposition being broken.

Overall, the paper has a false central claim for q≥3 and a broken proof for q=2, so the results are not established.

Extended reading notes

Core claim

Theorem 2.11: 'The symmetric group of basis vectors {b1,b2,...,bn} is isomorphic to the automorphism group of G(V).' The abstract repeats this without qualification. If true for all finite fields, a graph's symmetries would be precisely the reorderings of its basis. This claim is false for q≥3.

Load-bearing premise

Corollary 2.10: 'Every automorphism of G(V) can be restricted to a permutation of basis vectors.' This assumes automorphisms map the chosen basis {b1,...,bn} to itself. Over fields with q≥3, a monomial automorphism can send b1 to c b1 with c≠0, which is not in the basis. The assumption enters the proof of Theorem 2.11 and the isomorphism claim, and fails for q=3, n=3.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear Colleague,

I read the paper and the reader's report. I agree with the reject verdict, and the stress-test note is right on target. The central claim—Theorem 2.11 and the abstract's unqualified statement that the symmetric group of basis vectors is isomorphic to Aut(G(V))—is false for q≥3. A monomial map sending each basis vector to a nonzero scalar multiple of a permuted basis vector preserves support intersections, so it is an automorphism; for q≥3 these maps are not just permutations of the basis. For V=F_3^3, (x1,x2,x3) ↦ (2x1,x2,x3) fixes b2,b3 and sends b1 to 2b1, so it does not restrict to a permutation of the chosen basis. Corollary 2.10, used to prove onto-ness in Theorem 2.11, fails. The automorphism group is actually the monomial group of order (q-1)^n n!, so Theorem 2.12 is also off by a factor of (q-1)^n.

What is worth keeping: Theorem 2.9 correctly shows every basis permutation extends to an automorphism. For q=2, scalar multiples collapse, so the symmetric-group isomorphism and |Aut|=n! are valid. The distinguishing-number results are the new part, and the q=2 result Dist=2 is plausible, but the proof is not sound. Lemma 3.1 is invalid: two vertices with different labels being unable to map to each other does not break an automorphism that sends one of them to a third vertex with the same label. The verification in the T_{n-1} step of Theorem 3.2 also uses sets S_u and S_v that do not have size n-1. For q≥3, Dist=(q-1)^n is actually the right answer, but the paper's twin-set labeling proof is incomplete; the clean argument is that labeling the largest twin set (all full-support vectors) injectively is already distinguishing, since the monomial action is faithful on that set.

The paper leans heavily on self-citations [5] and [15] for its key lemmas, but the main failure is mathematical, not bibliographic. The intended audience is researchers working on symmetry breaking in graphs from vector spaces; a corrected version could be a minor contribution. As it stands, the main theorem is false and the q=2 proof has real gaps. I wouldn't send this to peer review; a desk reject is justified, with an invitation to resubmit a corrected version.

Referee Report

5 major / 6 minor

Summary. The paper studies the non-zero component graph G(V) associated with a finite-dimensional vector space V over a field with q elements. The main claims are: (1) every permutation of a fixed basis extends to an automorphism of G(V); (2) the symmetric group on the basis vectors is isomorphic to Aut(G(V)); (3) consequently |Aut(G(V))|=n!; (4) the distinguishing number is 2 when q=2 and n≥3; and (5) the distinguishing number is (q−1)^n when q≥3 and n≥3. The abstract states the isomorphism and cardinality results without any restriction on q, while Section 2 begins by restricting attention to the field with two elements. Section 3 treats the q=2 and q≥3 cases separately, using a labeling argument for q=2 and a twin-set argument for q≥3.

Significance. If fully established, the results would provide a complete description of the automorphism group and the distinguishing number of non-zero component graphs, a natural and useful contribution to the study of graphs associated to vector spaces. The paper does not include machine-checked proofs or reproducible code; its contribution is purely mathematical. Some parts are likely correct, in particular the q=2 automorphism result (which follows from earlier work of Das and of the authors' group) and the lower bound in the q≥3 distinguishing result. However, the manuscript as written contains false unqualified statements and a central proof (Theorem 3.2) that relies on a false lemma, so the claimed results are not supported as stated.

major comments (5)

[Abstract and §2, Theorem 2.11 and Theorem 2.12] The isomorphism Sym ≅ Aut(G(V)) and the consequence |Aut(G(V))|=n! are false when q≥3. For example, over F_3 with n=3, the map φ(x1,x2,x3)=(2x1,x2,x3) is an automorphism of G(V): it is bijective on nonzero vectors and preserves skeletons, hence preserves adjacency and non-adjacency. This automorphism sends b1 to 2b1, which is not one of the chosen basis vectors, so it is not induced by a permutation of {b1,b2,b3}. The monomial group (F_q^×)^n ⋊ S_n is contained in Aut(G(V)) for q≥3. The introduction to Section 2 explicitly restricts to fields with two elements, but the abstract and the statements of Theorem 2.11 and Theorem 2.12 do not carry this restriction. This is a load-bearing overgeneralization that must be corrected throughout the paper.
[§2, Theorem 2.9] The extension construction in Theorem 2.9 is not well-defined for q≥3. The proof defines g(u) as 'a vector whose skeleton is {h(b1),...,h(bm)}'; when q>2 there are (q−1)^m distinct vectors with that skeleton, so the image of u is not uniquely specified. The construction works only when q=2, where each skeleton determines a unique vector. The theorem statement and its proof require the hypothesis q=2 (or an explicit rule for transforming the coefficients).
[§3, Lemma 3.1] Lemma 3.1 is false as stated. Take n=6, q=2, u=b1+b3+b5, v=b2+b3+b6, and let g be the automorphism that swaps b1 and b2 and fixes all other basis vectors. Then b1∈S_u\S_v and b2∈S_v\S_u. Define a 2-labeling f by f(u)=f(g(u))=1, f(v)=f(g(v))=2, and f(w)=1 for all other vertices. Then f(u)≠f(v), but g preserves f, so f does not break g even though g maps b1 and b2 to each other. The deduction in the proof, that because u and v cannot map to each other Lemma 2.6(i) prevents b_l and b_m from mapping to each other, is invalid: an automorphism swapping b_l and b_m need not send u to v.
[§3, Theorem 3.2, step (2)] The labeling of T_{n−1} is incorrect. The sets S_u={b2,b3,...,b_{⌊n/2⌋}} and S_v={b1,b3,b4,...,b_{⌊n/2⌋}} have size ⌊n/2⌋−1 and ⌊n/2⌋−1 respectively, not n−1, so these vertices do not belong to T_{n−1} for n≥5. Thus the proposed labels do not apply to the intended class, and the claimed destruction of the transposition (b1 b2) is not established.
[§3, Theorem 3.4] The proof of Theorem 3.4 is incomplete. The statement that each twin set T_i^k is labeled with (q−1)^i labels 'out of' the (q−1)^n available labels, and that this destroys all automorphisms of disjoint twin sets, does not address automorphisms that map one twin set to another. If two twin sets receive the same set of labels, a nontrivial automorphism could map one to the other while preserving labels. The result is likely true — an injective labeling of T_n with (q−1)^n colors would break every automorphism — but the argument as written needs to be replaced by a rigorous global construction.

minor comments (6)

[Abstract] The phrase 'for both of the cases' should read 'in both cases'.
[§1, last sentence of introduction] There is a grammatical error: 'properties of automorphisms non-zero component graphs' should be 'properties of automorphisms of non-zero component graphs'.
[§3, Theorem 3.4 statement] The statement reads 'Let GV be the non-zero component graph'; it should be 'Let G(V) be the non-zero component graph'.
[Throughout] The paper repeatedly refers to 'we' in describing results from references [5] and [15] (e.g., Lemmas 2.2–2.6 and the partition into classes T_i). These should be attributed in the third person, e.g., 'it was shown in [5]'.
[§2, proof of Theorem 2.11] In the well-definedness part (1), the proof assumes that for a vertex u∈T_m the skeleton is S_u={b1,...,bm}. This is only true after relabeling the basis; the proof should say 'without loss of generality'.
[References] Reference [12] contains the typo 'functi-graphs'; it should be 'function graphs'.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on prior structural results about automorphisms of non-zero component graphs; no free parameters are fitted. The main unsupported step is the assertion that automorphisms permute the chosen basis, which fails over larger fields.

assumptions (4)

domain assumption Theorem 1.1 (Das [9]): Every automorphism of G(V) maps a basis to a basis of the form {c_i α_{σ(i)}} with c_i non-zero.
Used as foundation for the automorphism analysis in Section 1.
domain assumption Lemmas 2.1 to 2.6 and Remark 2.3 from [5] and [15] are taken as established black boxes, including skeleton-adjacency lemmas.
These lemmas are cited from the authors' own prior work and are not proved in this paper; the central proofs rest on them.
ad hoc to paper Corollary 2.10 assumes that the image of each chosen basis vector under an automorphism is again one of the chosen basis vectors.
This is asserted without proof and is false for q≥3; it is load-bearing for Theorem 2.11.
standard math Proposition 3.3 from [12] gives the twin-set lower bound Dist(G) ≥ max twin size.
Used in Theorem 3.4 for the lower bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distinguishing Number of Non-Zero Component Graphs." pith.science (2026). https://pith.science/paper/MENFMDQ5

@misc{pith2026190801001,
  author       = {Pith},
  title        = {Pith review of: Distinguishing Number of Non-Zero Component Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MENFMDQ5}},
  note         = {Machine review of arXiv:1908.01001}
}

abstract

A non-zero component graph $G(\mathbb{V})$ associated to a finite vector space $\mathbb{V}$ is a graph whose vertices are non-zero vectors of $\mathbb{V}$ and two vertices are adjacent, if their corresponding vectors have at least one non-zero component common in their linear combination of basis vectors. In this paper, we extend the study of properties of automorphisms of non-zero component graphs. We prove that every permutation of basis vectors can be extended to an automorphism of $G(\mathbb{V})$. We prove that the symmetric group of basis vectors of $\mathbb{V}$ is isomorphic to the automorphism group of $G(\mathbb{V})$. We find the distinguishing number of the graph for both of the cases, when the number of field elements of vector space $\mathbb{V}$ are 2 or more than 2.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[5]

Benish, I

H. Benish, I. Javaid, M. Murtaza, Automorphism related parame ters of a graph associated to a ﬁnite vector space, accepted for publication in Utilitas Mathematic a

work page
[15]

Murtaza, I

M. Murtaza, I. Javaid and M. Fazil, Locating-dominating sets an d identifying codes of a graph associated to a ﬁnite vector space, arXiv preprint arXiv:1701.0853 7, (2017). 9

work page arXiv 2017
[1]

M. O. Albertson, K. Collins, Symmetry breaking in graphs, Electron. J. Combin., 3 (1996), R 18

work page 1996
[2]

U. Ali, S. A. Bokhary, K. Wahid, G. Abbas, On resolvability of a grap h associated to a ﬁnite vector space, J. Algebra Appl. , 1950029

work page
[3]

Bates, D

C. Bates, D. Bondy, S. Perkins and P. Rowley, Commuting involutio n graphs for symmetric groups, J. Algebra., 266(2003), 133-153

work page 2003
[4]

Beck, Coloring of commutative rings, J

I. Beck, Coloring of commutative rings, J. Algebra., 116(1988), 208-226

work page 1988
[6]

Bondy, The connectivity of commuting graphs, J

D. Bondy, The connectivity of commuting graphs, J. Combin. Theory Ser. A. , 113(2006), 995-1007

work page 2006
[7]

P. J. Cameron and S. Ghosh, The power graph of a ﬁnite group, Disc. Math. , 311(2011), 1220-1222

work page 2011

Show all 17 references

[8]

Chakrabarty, S

I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power gra phs of semi group, Semi group. Forum., 78(2009), 410-426

2009
[9]

Das, Non-Zero component graph of a ﬁnite dimensional vecto r space, Communi

A. Das, Non-Zero component graph of a ﬁnite dimensional vecto r space, Communi. in Algebra., 44(2016), 3918-3926

2016
[10]

Das, On non-zero component graph of vector spaces over ﬁnite ﬁelds, J

A. Das, On non-zero component graph of vector spaces over ﬁnite ﬁelds, J. Algebra Appl. , 2016, 1750007

2016
[11]

Fazil, Determining sets and related parameters in graphs, Ph D Thesis

M. Fazil, Determining sets and related parameters in graphs, Ph D Thesis
[12]

Fazil, M

M. Fazil, M. Murtaza, Z. Ullah, U. Ali and I. Javaid, On the distingu ishing number of functi- graphs, Symmetry, 10(8), 2018, p.332

2018
[13]

Jafari Rad and S

N. Jafari Rad and S. H. Jafari, Results on the intersection gra phs of subspaces of a vector space, http://arxiv.org/abs/1105.0803v1

arXiv
[14]

A. R. Moghaddamfar, S. Rahbariyan and W. J. Shi, Certain prop erties of the power graph associated with ﬁnit group, J. Algebra Appl. , 13(2014), 450040

2014
[16]

Rubin, The blind man’s keys

F. Rubin, The blind man’s keys. Journal of Recreational Maths 1 2(1980)

1980
[17]

Talebi, M.S

Y. Talebi, M.S. Esmaeilifar and S. Azizpour, A kind of intersection g raph of vector space, J. Disc. Math. Sci. Crypt., 12, 6(2009), 681-689. Centre for advanced studies in Pure and Applied Mathematics , Bahauddin Za- kariya University Multan, Pakistan Email: ijavaidbzu@gmail....

2009

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [5]

Benish, I

H. Benish, I. Javaid, M. Murtaza, Automorphism related parame ters of a graph associated to a ﬁnite vector space, accepted for publication in Utilitas Mathematic a

work page

[2] [15]

Murtaza, I

M. Murtaza, I. Javaid and M. Fazil, Locating-dominating sets an d identifying codes of a graph associated to a ﬁnite vector space, arXiv preprint arXiv:1701.0853 7, (2017). 9

work page arXiv 2017

[3] [1]

M. O. Albertson, K. Collins, Symmetry breaking in graphs, Electron. J. Combin., 3 (1996), R 18

work page 1996

[4] [2]

U. Ali, S. A. Bokhary, K. Wahid, G. Abbas, On resolvability of a grap h associated to a ﬁnite vector space, J. Algebra Appl. , 1950029

work page

[5] [3]

Bates, D

C. Bates, D. Bondy, S. Perkins and P. Rowley, Commuting involutio n graphs for symmetric groups, J. Algebra., 266(2003), 133-153

work page 2003

[6] [4]

Beck, Coloring of commutative rings, J

I. Beck, Coloring of commutative rings, J. Algebra., 116(1988), 208-226

work page 1988

[7] [6]

Bondy, The connectivity of commuting graphs, J

D. Bondy, The connectivity of commuting graphs, J. Combin. Theory Ser. A. , 113(2006), 995-1007

work page 2006

[8] [7]

P. J. Cameron and S. Ghosh, The power graph of a ﬁnite group, Disc. Math. , 311(2011), 1220-1222

work page 2011