具有最小反对称分割指数的化学树

设图$G$,其中边集为$E(G)$,顶点集$V(G)$.反对称分割指数被定义为$ISDD(G)=\sum_{uv \in E(G)}\dfrac{d_ud_v}{d_u^2+d_v^2}$,其中$d_u$, $d_v$分别为顶点$u,v$的度.化学树就是顶点的度不超过4的树.在本文中,我们刻画出具有最小反对称分割指数的$n$阶化学树.     

$k$-广义拟树的第一个leap Zagreb 指标

图$G$的第一个leap Zagreb指标定义如下: $LM_1(G)=\sum_(v\in v(G)}d_2(v/G)^2$, 其中$d_2(v/G)$是离点$v$的距离为2的顶点. 令$\mathcal{QT}^{(k)}(n)$是有$n$个顶点的$k$-广义拟树的集合.若$G\in \mathcal{QT}^{(k)}(n)$, 本文给出了图$G$的第一个leap Zagreb指标的范围.     

图加一条边后的带宽和

令$BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$, 其中$f$为$V(G)\rightarrow\{1,2,\cdots,|V(G)|\}$的双射, 并称$BS(G)=\min\limits_{f}BS(G,f)$为图$G$的带宽和. 讨论顶点数为$n$的简单图$G$加上一条边$e\in\overline{E(G)}$后, 带宽和$BS(G+e)$与$BS(G)$的关系, 得其关系式$BS(G)+1\leq BS(G+e)\leq BS(G)+n-1$. 并证明此不等式中等号可取到, 即存在图$G_{1}$和$G_{2}$使得$BS(G_{1}+e)=BS(G_{1})+1$, $BS(G_{2}+e)=BS(G_{2})+n-1$.     

关于线图和全图的原子键连通性指数

连通图G的原子键连通性(ABC)指数定义为: ABC(G)=\sum\limits_{uv\in E(G)} \sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}} , 其中E(G)为图G的边集, d(u) 和d(v)为顶点u和v的度数. 原子键连通性指数是化学图论中比较重要的连通度指数, 最近的研究表明它可以用来研究烷烃的能量信息. 给出了线图和全图的ABC指数的上界和下界, 并且证明了这些界是可达的.     

图的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)$的谱性质.     

一类缺项算子矩阵的四类点谱的扰动

有界线性算子的点谱可进一步细分为4类,分别为$\sigma_{p1}$, $\sigma_{p2}$, $\sigma_{p3}$ 和$\sigma_{p4}$.设 $H, K$为无穷维可分的Hilbert空间,用$M_C$表示$2\times 2$上三角算子矩阵$\left(\begin{array}{cc} A & C \\ 0 & B \\ \end{array} \right)$,对于给定的 $A\in B(H),~B\in B(K)$,描述了集合$\bigcap\limits_{C\in B(K,H)}\sigma_{p1}(M_C)$, $\bigcap\limits_{C\in B(K,H)}\sigma_{p2}(M_C)$, $\bigcap\limits_{C\in B(K,H)}\sigma_{p3}(M_C)$和$\bigcap\limits_{C\in B(K,H)}\sigma_{p4}(M_C)$.     

一个关于平面图的K-(2,1)-全可选性的结果

设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$.     

图的上可嵌入性与围长及相邻顶点度和

$G$是一个阶为$n$围长为$g$的简单图, $u$和$v$是$G$中任意两个相邻顶点, 如果$d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 5$, 则$G$是上可嵌入的; 如果$G$是2-\!边连通(或3-\!边连通)图, 则当 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 3$ (或 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g - 5$)时$G$是上可嵌入的, 并且上面3个下界都是紧的.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

图的邻点强可区别的全染色

设 $G(V, E)$是阶数不小于~3 的简单连通图, $k$ 是自然数, $f$ 是从~$V(G)\cup E(G)$到 ~$\{1, 2, \dots, k\}$ 的映射, 满足: 对任意的 ~$uv\inE(G),f(u)\not= f(v), f(u)\not= f(uv)\not= f(v)$; 对任意的$uv,uw\in E(G)\,(v\neq w), f(uv)\neq f(uw)$; 对任意的$uv\in E(G), C(u)\neq C(v)$, 其中$C(u)=\{f(u)\}\cup \{f(v)|uv\in E(G)\}\cup \{f(uv)|uv\in E(G)\}$, 则称$f$是图$G$ 的一个邻点强可区别的全染色法. 简记作 $k$-AVSDTC, 且称 $ \chi_{\rm ast}(G)=\min\{k\mid G \textrm{ 的所有 }\ k\textrm{-AVSDTC}\} $ 为$G$ 的邻点强可区别的全色数. 得到了圈、完全图、完全二部图、树的邻点强可区别全色数.     

树的导出匹配覆盖

The induced matching cover number of a graph G without isolated vertices,denoted by imc(G),is the minimum integer k such that G has k induced matchings M1,M2,…,Mk such that,M1∪M2 ∪…∪Mk covers V(G).This paper shows if G is a nontrivial tree,then imc(G) ∈ {△*0(G),△*0(G) + 1,△*0(G)+2},where △*0(G) = max{d0(u) + d0(v) :u,v ∈ V(G),uv ∈ E(G)}.     

单圈图的最大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.     

图的邻点可区别全色数的一个上界

Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, where
C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.
Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.     

单圈图的最大特征值的上界的改进

Let G（V, E） be a unicyclic graph, Cm be a cycle of length m and Cm G, and ui ∈ V（Cm）. The G - E（Cm） are m trees, denoted by Ti, i = 1, 2,..., m. For i = 1, 2,..., m, let eui be the excentricity of ui in Ti and ec = max{eui ： i = 1, 2 , m}. Let κ = ec＋1. Forj = 1,2,...,k- 1, let δij = max{dv ： dist（v, ui） = j,v ∈ Ti}, δj = max{δij ： i = 1, 2,..., m}, δ0 = max{dui ： ui ∈ V（Cm）}. Then λ1（G）≤max{max 2≤j≤k-2 （√δj-1-1＋√δj-1）,2＋√δ0-2,√δ0-2＋√δ1-1}. If G ≌ Cn, then the equality holds, where λ1 （G） is the largest eigenvalue of the adjacency matrix of G.     

关于图的符号边全控制数

Let G = （V,E） be a graph.A function f ： E → {-1,1} is said to be a signed edge total dominating function （SETDF） of G if e ∈N（e） f（e ） ≥ 1 holds for every edge e ∈ E（G）.The signed edge total domination number γ st （G） of G is defined as γ st （G） = min{ e∈E（G） f（e）｜f is an SETDF of G}.In this paper we obtain some new lower bounds of γ st （G）.     

几乎无爪图的叶子数较少的生成树

A spanning tree with no more than 3 leaves is called a spanning 3-ended tree.In this paper, we prove that if G is a k-connected(k ≥ 2) almost claw-free graph of order n and σ_(k+3)(G) ≥ n + k + 2, then G contains a spanning 3-ended tree, where σk(G) =min{∑_(v∈S)deg(v) : S is an independent set of G with |S| = k}.     

环状硅酸盐图的友好指数集

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f : V(G) →Z2 induces an edge labeling f*: E(G) → Z2 defined by f*(xy) = f(x) + f(y), for each edge xy ∈ E(G). For i ∈ Z2, let vf(i) = |{v ∈ V(G) : f(v) = i}| and ef(i) = |{e ∈ E(G) : f*(e) =i}|. A labeling f of a graph G is said to be friendly if |vf(0)- vf(1)| ≤ 1. The friendly index set of the graph G, denoted FI(G), is defined as {|ef(0)- ef(1)|: the vertex labeling f is friendly}. This is a generalization of graph cordiality. We investigate the friendly index sets of cyclic silicates CS(n, m).