不含三圈作为导出子图秩为5的符号图的结构刻画

On Triangle-free Signed Graphs with Rank 5

令Γ=(G,σ)表示一个以G=(V(G),E(G))为基图,符号函数为σ:E(G)→{+,-}的符号图。一个符号图Γ的邻接矩阵的正特征值和负特征值的个数(包含重数),用符号p(Γ)和n(Γ)来表示,分别称作符号图Γ的正惯性指数和负惯性指数。符号图Γ的正惯性指数p(Γ)和负惯性指数n(Γ)的和称作符号图Γ的秩,用符号r(Γ)表示。如果符号图Γ的基图G是一个不含三圈作为导出子图的图,那么称Γ=(G,σ)是不含三圈作为导出子图的符号图。文章将完整地刻画出不含三圈作为导出子图的秩为5的符号图。

LetΓ=(G,σ)be a signed graph with underlying graph G=(V(G),E(G))and sign functionσ:E(G)→{+,-}.The numbers of positive eigenvalues and negative eigenvalues(including multiplicities)of the adjacent matrix ofΓ,denoted by p(Γ)and n(Γ),is called the positive inertia index and negative inertia index ofΓ,respectively.The sum of p(Γ)and n(Γ)is called the rank ofΓ,denoted by r(Γ).We callΓ=(G,σ)trianglefree if G does not contain triangle as its induced subgraph.In this paper,the triangle-free signed graphs with rank 5 are completely characterized.