两类树图上的Randi?指标与Harmonic指标之差的极值

设G=(V,E)为简单无向连通图.F_R,H(G)为图G的Randi?指标(R(G))与Harmonic指标(H(G))之差.分别确定了F_R,H(G)在二叉树上的前三大极值,及其在化学树上的前六大极值.     

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

图的2-控制数的上界和一个Graffiti.pc猜想（英文）

设G=(V(G),E(G))是一个图,k是一个正整数.称一个顶点子集S为G的kk-控制集,若V(G)\S中的每个顶点在S中至少有k个邻点,我们用r_k (G)表示kk-控制集的最小阶数.令d₁≤d₂≤…≤d_n为图G的度序列.当n为偶数时,度序列中位数m(G)=d_n/2+1,当n为奇数时,度序列中位数m(G)=d_n+1/2.一个仍未解决的Graffiti.pc猜想说:对任一n个顶点的连通图G,r₂(G)≤n-m(G)+1.首先我们证明了此猜想的一个弱形式:r2(G) ≤n-d₁+1.此外,通过拓展此猜想在二部图上的结果,我们证明了对最小度不小于2的无三角形图G,r2(G)≤n-Δ(G),其中Δ(G)为图G的最大度.众所周知,每一个其边数不少于顶点数的图都包含一个圈.我们将此结论推广到超图上.进而得到上述猜想对所有分裂图都成立.     

两类网络的2-限制连通度

给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G-S不连通且G-S中任一点的度数至少为h.图G的h-限制连通度κ~h(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ~2(FCQ_n)=4n-4 (n≥8),κ~2(SQn)=4n-8(n≥4),其中FCQ_n和SQ_n分别是n维折叠交叉超立方体和n维spined cube.     

关于图的余树的奇连通分支数的内插定理

本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.     

关于第二类Zagreb指数猜想的一个证明

设G是一个n阶简单图.G的第二类Zagreb指数定义为M₂(G)=■d_id_j.其中d_i表示顶点i的度.Xu等(2014)提出了一个关于第二类Zagreb指数的猜想:在所有阶数为n、边数为m的图中,M₂(G)最大的图是拟完全的.借助于门槛图的Ferrers表的性质,本文将上述猜想转化为组合矩阵论优化问题,并给出该猜想的一个代数证明.     

关于n-连通图的完美匹配与最大匹配

ξ1.引言本文所考虑的图均指无自环、无重边、无向有限的连通图,没有特别指明的术语见[1].以V(G)、E(G)分别表示图C的顶点集与边集. 设M是图G的一个支撑子图.若M的每个顶点的度是0或者1,则称M是G的一个匹配,若M是G的匹配中边数最多的一个,则称M是G的一个最大匹配;若M是G的匹配,且M中无0度顶点,则称M是G的一个完美匹配. 图G称为n连通的,若对G的任意两个不同的顶点x,y,G中存在n条以x,y为端点     

最大度为4的图的无圈列表边染色

对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e₁,e₂满足φ(e₁)≠φ(e₂),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’_l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’_l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果.     

张量积图的Tutte多项式及其应用

图G为具有m条边的连通图,E(G)={e₁,e₂,…,e_m},H={H₁,H₂,…,H_m}为由m个连通图构成的集合.图G[H]为G与H的张量积图,即对每个i(1≤i≤m),e_i被H_i替代而得到的图.张量积这一图运算包含了多个边替代图运算,例如细分、三角化、钻石化等图运算.本文中,我们给出了G[H]的Tutte多项式的显式表达式,进而得到了细分图、三角化图、钻石化图等运算图的Tutte多项式和生成树数目.     

高校应用数学学报第15卷(2000年)B辑(英文版)第3期目次和提要

3-边连通非简单图的最大亏格的一个注记黄元秋 (湖南师范大学数学系 )设 G为 3-边连通图 (不排除重边或环 ) ,且设γM( G)和β( G)分别为 G的最大亏格和 Betti数 .本文证明了γM( G)≥13β( G) ,从而回答了 Chen,Archdeacon及 Gross在 1996年所提出的一个问题 .整图的构造王力工　李学良　张胜贵 (西北工业大学应用数学系 )用两种新的方法给出了一些整图新类 ,也证明了寻找此类整图的问题与求解不定方程的问题是等价的 .其中一些整图类是具有无穷多个的 .这些图的发现是对寻找此类整图的一个新的贡献 .一类超二次二阶 Hamilton系统的…     

关于图的符号边全控制数

引入了图的符号边全控制的概念,给出了一个连通图G的符号边全控制数γs′t(G)的下限,确定所有n阶树T的最小符号边全控制数,并刻划了满足γs′t(G)=E(G)的所有连通图G,最后还提出了一个关于γs′t(G)上界的猜想.     

c-圈图的Laplace谱半径和最大度

设G是一个n阶的简单连通图,符号(d_1,d_2,...,d_n)表示G的度序列,其中d_1≥d_2≥···≥d_n,用符号?(G)表示G的最大度,而符号λ(G)表示G的Laplace谱半径.一个c-圈图是一个恰有n+c-1条边的n阶简单连通图,而符号C(n,?;c)表示最大度等于?的所有n阶c-圈图的集合.本文确定了当0≤c≤1/2(?-1)(?-2)时,C(n,?;c)中所有取得最小Laplace谱半径的极图,并分别确定了当?≥[n+2/3]且d_4≥2或?≥[n/3]+1且d_4=1时,C(n,?;1)中唯一取得最大Laplace谱半径的极图.进一步地,还证明了对于两个n阶的单圈图G和G′,如果?(G)≥[11n/30]+2且?(G)?(G′),则λ(G)λ(G′),并且界"[11n/30]+2"是最佳的.     

利用计算机计算n阶图的特征多项式的方法

1引言设G=（V,E）为n阶无向的简单连通图.记N（v）为v的所有相邻点的集合,则d（v）=|N（v）|称为顶点v的度.若d（v）=1,则称v为G的一个悬挂点.设D（G）=diag（d（v₁）,d（v₂）,…,d（v_n））和A（G）分别表示图G的度对角矩阵和邻接矩阵,则L（G）=D（G）-A（G）称为图G的Laplace矩阵,而Q（G）=D（G）+A（G）称为图G的SignlessLaplace矩阵.用符号N_m×n表示一个m行n列的矩阵,M_n表示一个n阶的方阵.特     

给定P3的无桥图的定向直径

设G是一个无向多重图,G的定向直径是指G的所有强连通定向中直径的最小值.Dankelmann,Guo,Surmacs [J.Graph Theory,2018,88:5-17]证明了n阶无桥图G的定向直径至多为n-Δ+3,这里Δ是G的最大度.设H是G的一个生成子图,定义■,利用上述结论他们还证明了,给定边e的无桥图G的定向直径至多为n-|N_G(e)|+5,以及给定无桥子图H的无桥图G的定向直径至多为n-|N_G(H)|+3.设P₃=uvw是G的一条长为2的路.易见P3包含两条边且这两条边均是P3的桥.本文利用将一条路收缩为一点的方法证明了给定P3的无桥图G的定向直径的上界为n-|N_G(P₃)|+5.特别地,若P3在一个4圈上或P3不在一个圈上但uv,vw分别在一个3圈上,定向直径至多为n-|N_G(P₃)|+4.最后举例说明了上述上界是紧的.     

给定直径的单圈图的边修正Szeged指标的下界

连通图G的边修正Szeged指标Sz_e^*(G)定义为■,其中m_u(e|G),m_v(e|G),m₀(e|G)分别是G中到u点比到v点距离近的边的数目、到v点比到u点距离近的边的数目、以及到u,v两点距离同样近的边的数目.本文通过变换和计算得到了给定直径的单圈图的边修正Szeged指标的下界,并刻画了达到下界的极值图.     

最大匹配数的一个问题

一、本文仅讨论简单图。图G的1-因子数记为F(G)。 f(G)记使如下事实正确的最大的K:“假如G是一个n-连通图且G有1-因子,则G至少有k个1-因子”。包含G的所有的点,且每个点的度为0或1的G的子图叫G的一个匹配M,有最大的边数的匹配称为最大匹配。假如匹配M的一个点v的度为0,称v为在M里的分离点。以M(G)表示G的最大匹配的集合。假如图G的一个点v所关连的每一条边都属于G的一个最大匹配,称点v被M(G)完全覆盖。     

关于极大外平面图的度偏差的极值

设G是一个由n个顶点,m条边构成的简单连通图.如果图G所有顶点的度相同,则我们称图G是正则图,反之,称图G是不规则图.对于一个不规则图G,由其不变量定义的度偏差为s(G)=∑_(i=1)^(n)|d_(i)-2m/n|,其中d_(i)表示G的第i个顶点的度.本文给出极大外平面图的度偏差的极大值和极小值,并刻画其对应的极值图.     

图的最小特征值（英文）

设图G是一个简单图,G的邻接矩阵用A(G)表示,A(G)的最小特征值λ_min(G)被称为G的最小特征值.首先建立了图的邻接矩阵的边数与最小特征值之间的关系,然后给出具有Hamiltonian路径或Hamiltonian圈的一些谱条件,或是Hamilton连通的,或是从每个顶点追踪到图的邻接矩阵的最小特征值.这为研究图的结构性质提供了一种行之有效的方法.     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G1,G2,且|G1 |≥2,|G2 |≥2,则称T是G的一个非平凡点割.假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图.证明了对任意一个k≥5且t＞k/2的整数,若G是一个不含(K2+tK1)的k-连通图,且G中任...     

具有弱specification性质的amenable群作用的拟弱几乎周期点的回复层次（英文）

设(X,G)是一个G-系统,{F_n}_n=1^∞是G的一个F?lner序列.本文证明了如果(X,G)具有强specification性质,则在(X,G)上存在一个相对于G的F?lner序列{F_n}_n=1^∞的真拟弱几乎周期点x和一个由x沿着{F_n}_n=1^∞的轨道生成的不变测度μ,使得μ的支撑与x的相对于F?lner序列{F_n}_n=1^∞的极小吸引中心相同.此外,如果(X,G)有弱specification性质且(X,G)的周期测度在(X,G)的不变测度集合M(X,G)中稠密,则在(X,G)上存在一个相对于G上的F?lner序列{F_n}_n=1^∞的真拟弱几乎周期点y,使得每一个由y的轨道沿F?lner序列{F_n}_n=1^∞...