单圈图的最大Balaban指数与最大和Balaban指数

The Balaban index of a connected graph G is defined as J(G) =|E(G)|μ + 1∑e=uv∈E(G)1√DG(u)DG(v),and the Sum-Balaban index is defined as SJ(G) =|E(G)|μ + 1∑e=uv∈E(G)1√DG(u)+DG(v),where DG(u) =∑w∈V(G)dG(u, w), and μ is the cyclomatic number of G. In this paper, the unicyclic graphs with the maximum Balaban index and the maximum Sum-Balaban index among all unicyclic graphs on n vertices are characterized, respectively.     

给定悬挂点数的双圈图中具有最小Hosoya指数的图

Let G be a graph. The Hosoya index Z（G） of a graph G is defined to be the total number of its matchings. In this paper, we characterize the graph with the smallest Hosoya index of bicyclic graphs with given pendent vertices. Finally, we present a new proof about the smallest Hosoya index of bicyclic graphs.     

关于极大$S^2NS$阵的一个注记

一个实方阵A称为是S2NS阵,若所有与A有相同符号模式的矩阵均可逆,且它们的逆矩阵的符号模式都相同．若A是S2NS阵且A中任意一个零元换为任意非零元后所得的矩阵都不是S2NS阵,则称A是极大S2NS阵．设所有n阶极大S2NS阵的非零元个数所成之集合为S(n),Z4(n)={1/2n(n-1) 4,…,1/2n(n 1)-1},除了2n 1到3n一4间的一段和Z4(n)外,S(n)得到了完全确定．本文将用图论方法证明Z4(n)∩S(n)=(?)．     

有向全图的幂敛指数和周期

设G是有向图,T(G)表示G的有向全图.本文得到了它们的幂敛指数k(G)和k(T)之间的关系:对任何有向图G,周期p(T(G))=1;当G是本原图时,k(T)≤k(G)+1,文中给出了取得k(G)+1的两类图;当G是无圈图时,k(T)=2k(G)-1,当G是有向圈时,k(T)=2|V(G)|-1,当G是强连通时得到了k(T)的一些估计.     

本原不可幂带号有向图的lewin数的界

如果存在正整数k使得对于D中任意两点u和v(允许u=v),在D中都有从u到v的长为k的有向途径,则称有向图D是本原的.给有向图的每条弧赋以符号+1或者-1得到的图S称为带号有向图.如果带号有向图S中包含SSSD途径对,即包含两条有相同的起点,相同的终点,相同的长度,并且有不同的符号的途径对,则称S是不可幂的.在本文中,我们将Lewin M提出的lewin数的概念从本原有向图推广到本原不可幂带号有向图,给出了本原不可幂带号有向图S的lewin数l(S)的若干上界,并提出了一个公开问题.     

具有最小弧数且基指数为3的本原不可幂对称无环带号有向图

Let S be a primitive non-powerful symmetric loop-free signed digraph on even n vertices with base 3 and minimum number of arcs. In [Lihua YOU, Yuhan WU. Primitive non-powerful symmetric loop-free signed digraphs with given base and minimum number of arcs. Linear Algebra Appl., 2011, 434(5), 1215-1227], authors conjectured that D is the underlying digraph of S with exp(D) = 3 if and only if D is isomorphic to ED n,3,3 , where ED n,3,3 = (V, A) is a digraph with V = {1, 2, . . . , n}, A = {(1, i), (i, 1) | 3≤i≤n} ∪ {(2i-1, 2i), (2i, 2i-1) | 2≤i≤ n/2 } ∪ {(2, 3), (3, 2), (2, 4), (4, 2)}). In this paper, we show the conjecture is true and completely characterize the underlying digraphs which have base 3 and the minimum number of arcs.     

图的p-Sombor(拉普拉斯)矩阵的谱性质

最近在化学图论引入的Sombor指数可以预测分子的物理化学性质. 本文从代数的角度来研究($p$-)Sombor指数的性质. $p$-Sombor矩阵$\mathcal{S}_{p}(G)$是一个$n$阶方阵, 当$v_{i}\sim v_{j}$时, 其$(i,j)$位置的元素为$((d_{i})^{p}+(d_{j})^{p})^{\frac{1}{p}}$, 否则为$0$, 其中$d_{i}$表示图$G$中顶点$v_{i}$的度. 该矩阵推广了著名的Zagreb矩阵$(p=1)$、Sombor矩阵$(p=2)$和inverse sum indeg矩阵$(p=-1)$. 本文找到了一对$p$-Sombor非同谱的等能量图, 并确定了$p$-Sombor(拉普拉斯)谱半径的一些界. 然后刻画了具有$k$个不同$p$-Sombor拉普拉斯特征值的连通图的性质. 最后确定了一些特殊图的Sombor谱. 作为推论, 确定了Sombor矩阵$(p=2)$, Zagreb矩阵$(p=1)$和inverse sum indeg矩阵$(p=-1)$的谱性质.     

极大S2NS阵的分支数与非零元个数

一个实方阵A称为是S     

本原对称无环带号有向图的基指数与基指数集

In this paper,we study the bases and base sets of primitive symmetric loop-free (generalized)signed digraphs on n vertices.We obtain sharp upper bounds of the bases,and show that the base sets of the classes of such digraphs are{2,3,...,2n-1}.We also give a new proof of an important result obtained by Cheng and Liu.     

以完全二部图作为星补的正则图的刻画

设$G$是一个$n$阶图, $\mu$是$G$的一个$(k\ge 1)$重邻接特征值. 图$G$中关于$\mu$的星补$H$是指$G$的不含特征值$\mu$的$n-k$阶诱导子图,且顶点集$X=V(G-H)$称为图$G$中关于$\mu$的星集.星补技术提供了利用部分子结构来重建满足特定性质的整个图的谱工具. 本文我们研究了关于特征值$\mu$的以$K_{t,s}~(s\ge t\ge 2)$作为是补的正则图, 特别地, 我们完全刻画了$t=3$的情形, 获得了当$t=s$时的一些性质, 并提出了有待进一步研究的问题.