<p>We look for a non-zero (0, 1)-vector in the row space of the adjacency matrix <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1838_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$A(\Gamma )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of a graph <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1838_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma ,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Γ</mi> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> provided <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1838_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> has at least one edge. Akbari, Cameron, and Khosrovshahi conjectured that there exists a non-zero (0, 1)-vector in the row space of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1838_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$A(\Gamma )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> (over the real numbers) which does not occur as a row of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1838_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$A(\Gamma ).$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> This conjecture can be easily verified for graphs having diameter is equal to 1 (complete graphs). In this article, we affirmatively prove this conjecture for any graph whose diameter is <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1838_Article_IEq6.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="34" /> </InlineMediaObject> <EquationSource Format="TEX">$\ge 4.$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>≥</mo> <mn>4</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> Furthermore, in the remaining two cases that is, for graphs with diameter is equal to 2 or 3,  we report some progress in support of the conjecture.</p>

Existence of a Non-Zero (0, 1)-Vector in the Row Space of Adjacency Matrices of Simple Graphs

期刊论文
发表日期：

2025年2月24日

查看全文

S. Bera

摘要

We look for a non-zero (0, 1)-vector in the row space of the adjacency matrix $A(\Gamma )$ $A (Γ)$ of a graph $\Gamma ,$ $Γ,$ provided $\Gamma $ $Γ$ has at least one edge. Akbari, Cameron, and Khosrovshahi conjectured that there exists a non-zero (0, 1)-vector in the row space of $A(\Gamma )$ $A (Γ)$ (over the real numbers) which does not occur as a row of $A(\Gamma ).$ $A (Γ) .$ This conjecture can be easily verified for graphs having diameter is equal to 1 (complete graphs). In this article, we affirmatively prove this conjecture for any graph whose diameter is $\ge 4.$ $\geq 4 .$ Furthermore, in the remaining two cases that is, for graphs with diameter is equal to 2 or 3, we report some progress in support of the conjecture.