哈密顿线图的一个充分条件

对于图G的任意边e=uv,边的度定义为d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v的度.本文的主要结果是: 设G是几乎无桥的p≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为2的两边e_1和e_2,d(e_1)+d(e_2)≥2p-6,则G有一个D—闭迹,从而G的线图L(G)是哈密顿的.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

半无爪可迹图的度和条件

可迹图即为一个含有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,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.     

边色数的分类及其有关性质

设图G为简单连通图,由Vizing定理知:Δ(G)≤x′(G)≤Δ(G) 1,其中Δ(G)表示图G的最大顶点次,x′(G)为图G的边色数。若x′(G)=Δ(G),则称G为第一类图,记为G∈C~1;若x′(G)=Δ(G) 1,则称G为第二类图,记为G∈C~2。其他图论术语见一般参考书。一边e(或者顶点v)称为临界的,如果成立x′(G)>x′(G\e)(或者x′(G)>x′(G\v))。图G称为是临界的,如果G∈C~2,且G的每一边是临界的。对于v∈V(G),令d~*(v)=|{u|(v,u)∈E(G)且d(u)=Δ(G)}|。设F={u|d(u)=Δ(G),u∈V(G)},记G_Δ=G[F]。令图G_Δ的圈秩数为b(G_Δ)。     

广义图K(n,m)的点强全色数

图G(V,E)的一个正常k-全染色σ称为G(V,E)的一个k-点强全染色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u vu∈V(G)}∪{v};并且χvTs(G)=m in{k存在G的一个k-点强全染色}称为G的点强全色数.本文确定了完全图Kn的广义图K(n,m)和乘积图Lm×Kn的点强全色数.     

可圈的一个充分条件

本文我们证明如下结果:设G=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

若干图的强染色

图 G(V,E)的一正常 k-染色 σ称为 G(V,E)的 - k-强染色当且仅当对任何两个不同顶点 u和 v,只要d(u,v)≤ 2 ,则 u、v染不同颜色 (这里 d(u,v)表示 u,v之间的距离 ) ,并称 xs(G) =min{ k|存在 G的 - k-强染色 }为 G的强色数 ,本文得到 θ-图 ,Cm,n图 ,Halin图的强色数 xs(G)     

度为奇数的正则图的上负全控制数

f:v(G)→{一1,0,1}称为图G的负全控制函数,如果对任意点V∈V,均有f[v]≥1,其中 f[v]= ∑,f(u).如果对每个点v∈V,不存在负全控制函数g:V(G)→{-l,0,1),g≠f,满u∈N(v)足g(v)≤f(v),则称f是-个极小负全控制函数.图的上负全控制数F-t(G)=max{w(f)|f,是G的极小负全控制函数},其中w(f)=∑/v∈V(G)f(v).本文研究正则图的上负全控制数,证明了:令G是-个v∈V(G)n阶r-正则图.若r为奇数,则Γt-(G)＜＝r2 1/r2 2r-1n.     

图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S．G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数．G的下测地数g~-(G)=min{g(D)：D是G的定向图},G的上测地数g~ (G)=max{g(D)：D是G的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

2-连通半无爪图的最长圈

A graph G is called quasi-claw-free if it satisfies the property:d(x,y)=2 there exists a vertex u∈N(x)∩N(y)such that N[u]■N[x]∪N[y].In this paper,we show that every 2-connected quasi-claw-free graph of order n with G■F contains a cycle of length at least min{3δ+2,n},where F is a family of graphs.     

不含某些子图的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$ 可收缩边.     

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

$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$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.     

单圈图的极小能量

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un| d(x) = r for any vertex x ∈ V(Cl)}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39(2, 2, 2) ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

不含三角形图的$A_\alpha$-谱半径的界

设$G$是简单无向图. 对于实数$\alpha \in [0,1]$, Nikiforov于2017年定义图的$A_\alpha$-矩阵为$A_\alpha(G)=\alpha D(G)+(1-\alpha)A(G)$, 其中$A(G)$和$D(G)$分别为图$G$的邻接矩阵和度对角矩阵. 图的$A_\alpha$-矩阵可以看着是图的邻接矩阵和无符号拉普拉斯矩阵的共同推广, 其最大特征值称为图的$A_\alpha$- 谱半径. 对于$\alpha\in[0,1)$, 本文确定了不含三角形图的$A_\alpha$-谱半径的一个下界;对于$\alpha \in[1/2, 1)$, 本文确定了不含三角形$k$圈图的$A_\alpha$-谱半径的一个上界.     

二树的ABC指标

The atom-bond connectivity(ABC) index of a graph G, introduced by Estrada,Torres, Rodr′?guez and Gutman in 1998, is defined as the sum of the weights(1/di+1/dj-2/didj )~(1/2) of all edges vivj of G, where di denotes the degree of the vertex vi in G. In this paper, we give an upper bound of the ABC index of a two-tree G with n vertices, that is, ABC(G) ≤(2n- 4)2~(1/2)/2+(2n-4)~(1/2)/n-1. We also determine the two-trees with the maximum and the second maximum ABC index.     

关于完全二部图$K_{4, n}$和$K_{n, n}$的点可区别 $IE$-全染色的一些注记

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

补图是$r$-部的图的顶点可分解性质

Let G be a non-complete graph such that its complement G is r-partite.In this paper,properties of the graph G are studied,including the Cohen-Macaulay property and the sequential Cohen-Macaulay property.For r=2,3,some constructions are established for G to be vertex decomposable and some sufficient conditions are provided for r≥4.