正则图的邻强边染色和全染色

如果~$k$-\-正则图~$G$~不含~5-\-圈的分支, 则猜测~$\chi''_{\mathrm{as}}(G) = \chi_{\mathrm t}(G)$. 证明这个猜想对很多图类都成立, 例如: 第1类型图、 $2$-\-正则图、$3$-\-正则图、$(|V(G)|-2)$-\-正则图、二部图、完全等多部图、$k$-\-方体以及一些特殊的联图类等.     

$P_m\times K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.     

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

$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个下界都是紧的.     

一个关于平面图的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$的正常边染色称为无圈的, 如果图$G$中不含2-色圈, 图$G$的无圈边色数用$a''(G)$表示, 是使图$G$存在正常无圈边染色所需要的最少颜色数. Alon等人猜想: 对简单图$G$, 有$a''(G)\leq{\Delta(G)+2}$. 设图$G$是围长为$g(G)$的平面图, 本文证明了: 如果$g(G)\geq3$, 则$a''(G)\leq\max\{2\Delta(G)-2,\Delta(G)+22\}$; 如果 $g(G)\geq5$, 则$a''(G)\leq{\Delta(G)+2}$; 如果$g(G)\geq7$, 则$a''(G)\leq{\Delta(G)+1}$; 如果$g(G)\geq16$并且$\Delta(G)\geq3$, 则$a''(G)=\Delta(G)$; 对系列平行图$G$, 有$a''(G)\leq{\Delta(G)+1}$.     

边临界图的新下界

图$G$ 为简单的第二类连通图, 且对$G$ 的任意边$e$,有$\chi^{\prime}(G-e)<\chi^{\prime}(G)$, 则称 $G$是临界的.该文给出了阶为$n$ 边数为$m$的$\Delta$ -临界图的新下界, 即$m\geq(3\Delta+6)n/10$, 这里$1\leq\Delta\leq18$     

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

设 $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$ 的邻点强可区别的全色数. 得到了圈、完全图、完全二部图、树的邻点强可区别全色数.     

关于域的K2群的挠

设$F$是域, 记 $G_{n}(F)=\{\{a,
\Phi_{n}(a)\} \in K_{2}(F)\mid {a, \Phi_{n}(a)} \in F^{*}\},$
这里$\Phi_{n}(x)$ 是$n$次分圆多项式. 首先,
使用关于数域上的Mordell猜想的Faltings定理证明了若$F$是数域, $n\neq
1, 4, 8, 12$且含有平方因子, 则$G_{n}(F)$不是$K_{2}(F)$的子群; 然后,
使用Manin, Grauert, Samuel和李克正关于
函数域上的Mordell猜想的结果, 对代数闭域上的函数域证明了类似的结果.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

非负特征图的线性染色

如果图$G$的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图$G$ 的线性染色.图$G$的线性色数用lc$(G)$表示,是指$G$的所有线性染色中所用的最少颜色的个数. \qquad 证明了: 对于每一个最大度为$\Delta(G)$围长为$g(G)$的非负特征图$G$,若存在一个有序对$(\Delta,g)\in\{(13,7),(9,8),(7,9),(5,10), (3,13)\}$, 使得$G$满足$\Delta(G)\ge\Delta$且$g(G)\ge g$,则lc$(G)=\lceil \frac {\Delta(G)}2\rceil+1$.     

关于图中存在不含给定k-因子的[a,b]-因子的度条件

设$1\leq a<b, 0\leq k$是整数. 设$G$是一个含有$k$-因子$Q$且阶为$|G|$的图. 设\delta(G)$表示$G$的最小度, 且$\delta(G)\geq a+k$. 如果$Q$连通, 设$\varepsilon=k$, 否则设$\varepsilon=k+1$.证明:当$b\geq a+\varepsilon-1$时, 如果对$G$的任意两个不相邻的点$x$和$y$都有max$\{d_G(x),d_G(y)\}\geq {\rm max}\{{{a|G|} \over {a+b}},{{(|G|+(a-1)(2a+b+\varepsilon-2))} \over {b+1}}\}+k$, 那么$G$有一个$[a, b]$-因子$F$ 使得 $E(F)\cap E(Q)=\emptyset$. 这个度条件是最佳的, 条件$b\geqa+\varepsilon-1$不能去掉. 进一步,得到图存在含给定$k$-因子的$[a, b]$-因子的度条件.     

若干联图的均匀全染色

图$G(V,E)$的全色数 $\chi_{t}(G)$就是将$V\bigcup E$分成彼此不相交的全独立分割集的最小个数。 如果任何两个$V\bigcup E$的全独立分割集的元素数目相差不超过1，那么 $V \bigcup E$的全独立分割集的最小个数就称为图$G$的均匀全色数，记为$\chi_{et}(G)$。 在本文中我们给出了当 $m \geq n \geq 3$ 时 $W_m\bigvee K_n$，$F_m \bigvee K_n$及$S_m \bigvee K_n$ 的均匀全色数.     

半无爪可迹图的度和条件

可迹图即为一个含有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$\,是嵌入到欧拉示性数\,$\chi(\Sigma)\geq 0$\,的曲面\,$\Sigma$\,上的图, $\chi'(G)$\,和\,$\Delta(G)$\,分别表示图\,$G$\,的边色数和最大度. 如果\,$\Delta(G)\geq 4$\,且\,$G$\,满足以下条件: (1)\,图$G$中的任意两个三角形$T_1$, $T_2$的距离至少是$2$; (2)\,图\,$G$\,中\,$i$-圈和\,$j$-圈的距离至少是\,$1$, $i,j\in\{3,4\}$; (3)\,图\,$G$\,中没有\,$5$-圈, 则有\,$\Delta(G)=\chi'(G)$.     

双圈图的距离无符号拉普拉斯谱半径

连通图$G$的距离无符号拉普拉斯矩阵定义为$\mathcal{Q}(G)=Tr(G)+D(G)$, 其中$Tr(G)$和$D(G)$分别为连通图$G$的点传输矩阵和距离矩阵. 图$G$的距离无符号拉普拉斯矩阵的最大特征值称为$G$的距离无符号拉普拉斯谱半径. 本文确定了给定点数的双圈图中具有最大的距离无符号拉普拉斯谱半径的图.     

增益图与其底图的正惯性指数之间的关系

设$\mathbb{T}$是模为1的复数乘法子群.图$G=(V,E)$,这里$V,E$分别表示图的点和边.增益图是将底图中的每条边赋于$\mathbb{T}$中的某个数值$\varphi(v_iv_j)$,且满足$\varphi(v_iv_j) =\overline{\varphi(v_jv_i)}$.将赋值以后的增益图表示为$(G,\varphi)$.设$i_+(G,\varphi)$和$i_+(G)$分别表示增益图与底图的正惯性指数,本文证明了如下结论: $$ - c( G ) \le {i_ + } ( {G,\varphi } ) - {i_ + }( G ) \le c( G ), $$ 这里$c(G)$表示圈空间维数,并且刻画了等号成立时候的所有极图.     

关于三圈图的拉普拉斯谱半径的一些结果

边数等于点数加二的连通图称为三圈图.~设 ~$\Delta(G)$~和~$\mu(G)$~
分别表示图~$G$~的最大度和其拉普拉斯谱半径,设${\mathcal
T}(n)$~表示所有~$n$~阶三圈图的集合,证明了对于~${\mathcal
T}(n)$~的两个图~$H_{1}$~和~$H_{2}$~,~若~$\Delta(H_{1})>
\Delta(H_{2})$ ~且 ~$\Delta(H_{1})\geq \frac{n+7}{2}$,~则~$\mu
(H_{1})> \mu (H_{2}).$ 作为该结论的应用,~确定了~${\mathcal
T}(n)(n\geq9)$~中图的第七大至第十九大的拉普拉斯谱半径及其相应的极图.     

完全多部图的符号边控制数的界

$f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e''\in N[e]}f(e'')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.     

高度正则图的全着色

一个图$G$的全色数$\chi_T(G)$ 是对$G$的边和顶点着色的最小数, 使得相关联或相邻元素着不同色. 证明了如果$G$是正则图并且$d(G)\ge\cfrac{2}{3}|V(G)|+\cfrac{23}{6},$ 这里$d(G)$ 表示在$G$中顶点的度, 则$\chi_T(G)\leq d(G)+2$.     

关于乘积Sombor指数的极值(分子)树

拓扑指数是一类可以用来预测化合物的物理化学性质的数值不变量, 其并被广泛用于量子化学、分子生物学和其他研究领域. 对于一个顶点集为$V(G)$、边集为$E(G)$的(分子)图$G$, 其Sombor指数定义为$SO(G)=\sum\limits_{uv\in E(G)}\sqrt{d_{G}^{2}(u)+d_{G}^{2}(v)}$, 其中$d_{G}(u)$表示顶点$u$在$G$中的度. 相应地, 乘积Sombor指数定义为$\prod\nolimits_{SO}(G)= \prod\limits_{uv\in E(G)}\sqrt{d_{G}^{2}(u)+d_{G}^{2}(v)}$. 分子树是最大度$\Delta\leq 4$的树. 在本文中, 我们首先确定了乘积Sombor指数最大的分子树, 然后我们确定了乘积Sombor指数的前十三小的(分子)树.