Δ(G)≤4的外平面图的邻强边色数

研究了Δ(G)≤4的外平面图的邻强边染色,证明了Δ(G)≤χ′as(G)≤Δ(G)+1,且χ′as(G)=Δ(G)+1当且仅当存在两个最大度点相邻,其中Δ(G)和χ′as(G)分别表示图G的最大度和邻强边色数,并且提出了如下猜想:如果G是一个|V(G)|≥3(G≠C5)的2-连通图,则Δ(G)≤χ′as(G)≤Δ(G)+2.     

Δ(G)=4的Halin-图的邻强边染色(英文)

图 G(V,E)的一正常 k-边染色 f称为 G(V,E)的一 k-邻强边染色 (简称 k- ASEC)当且仅当任意uv∈ E(G)满足 f[u]≠f[v],其中 f[u]={ f(uw) | uw∈ E(G) } ,并称 χ′as(G) =min{ k|存在 G的一 k- ASEC}为G的邻强边色数 .本文研究了 Δ(G) =4的 Halin-图的邻强边染色 ,得到了如下结果 :对 Δ(G) =4的 Halin-图有 Δ(G) =4≤ χ′as(G)≤ Δ(G) + 1=5 .     

单形中的一类不等式

<正> 在ΔABC 中,设 BC=a,CA=b,AB=c,又 x_a,x_b,x_c 分别为三边 a,b,c 上的任一点至该边所对的顶点之间的线段,若ΔABC 的面积为Δ,则对于正实数 α,u,v(u≤v)有∑a~α(-ux_a~α+vx_b~α+vx_c~α)≥3(2v-u)2~αΔ~α.(1)当 x_a,x_b,x_c 分别为正ΔABC 的边 a,b,c 上的高时等号成立.在(1)中,特别地取 x 为ΔABC 的高线,内角平分线及中线时,则有∑a~α(-uh_a~α+vh_b~α+vh_c~α)≥3(2v-u)2~αΔ~α,(2)∑a~α(-ut_a~α+vt_b~α+vt_c~α)≥3(2v-u)2~αΔ~α,(3)∑a~α(-um_a~α+vm_b~α+vm_c~α)≥3(2v-u)2~αΔ~α.(4)当且仅当ΔABC 为正三角形时等号成立.若有两个ΔABC 和ΔA′B′C′的面积分别为Δ和Δ′,h_a,h_b,h_c 及 h_(a′),h_(b′),h_(c′)分别为     

给定最大度的单圈偶图的谱半径

单圈偶图是边数等于顶点数的简单连通偶图.Δ（G）表示图G的最大度.文中给出了最大度为Δ(≥ⁿ⁺¹/2)的n阶单圈偶图的谱半径的上界,并刻画了达到该上界的图.文中还证明了当Δ（G）≥[（2n+1）/3]+1时,n（≥8）阶单圈偶图G的谱半径随着最大度的递增而严格递增,并在此基础上给出了谱半径排在前17位的n（≥16）阶单圈偶图.     

最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.     

分数(g,f,m)-消去图的不相邻顶点领域并条件（英文）

一个图称为分数(g,f,m)-消去图若删除任意m条边后的剩余子图依然存在分数(g,f)-因子.本文证明若图G的阶为n,1≤a≤g(x)≤f(x)-Δ≤b-Δ对任意顶点x∈V(G)成立,δ(G)≥(b-Δ)(b+1)/a+2m,n≥(a+b)(2(a+b)+2m-1)/(a+Δ),且|N_G(x_1)∪N_G(x_2)|≥(b-Δ)n/(a+b),对任意不相邻顶点x_1和x_2都成立,则G是分数(g,f,m)-消去图.这个领域并条件在一定程度上是最好的.     

最大度不小于5的外平面图的邻强边染色

图G(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.     

系列平行图的邻强边色数

本文研究了系列平行图的邻强边染色.从图的结构性质出发,利用双重归纳和换色的方法证明了对于△(G)=3,4的系列平行图满足邻强边染色猜想;对于△(G)≥5的系列平行图G, 有△(G)≤x'as(G)≤△(G) 1,且x'as(G)=△(G) 1当且仅当存在两个最大度点相邻,其中△(G)和x'as(G)分别表示图G的最大度和邻强边色数.     

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

δ和△分别表示图G的最小度和最大度,利用概率方法研究点可区别IV-全色数的上界,证得如果δ≥2,δ≥61n△,n≤([16Δ(Δ-1)]~(δ-1))/(96π·δ~(δ+2)·(Δ+1)),那么x_(vt)~(iv)(G)≤16Δ(Δ-1).     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.     

A note on immersion minors and planarity

Graph minors play an important role in graph theory. The focus of this paper is on immersion minors and their relationship to planarity. In general, planar graphs can have non-planar immersion minors. This paper shows that by placing a simple restriction on the immersion-minor operations, all immersion minors of a planar graph are planar. This then allows one to easily obtain a characterization of planar graphs using immersion minors. A dual form of this characterization, as well as an extension to binary matroids, are also considered.     

Bisecting a 4-connected graph with three resource sets

Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T₁,T₂,…,T_k of nodes, called resource sets, where |T_i| is even for each i. The partition problem with k resource sets asks to find a partition V₁ and V₂ of the node set V such that the graphs induced by V₁ and V₂ are both connected and |V₁∩T_i|=|V₂∩T_i|=|T_i|/2 holds for each i=1,2,…,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k?3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K₄ as its subgraph, then a bisection exists and it can be found in O(|V|³log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.     

Enclosings of decompositions of complete multigraphs in 2-edge-connected r-factorizations

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G\left(1\right),\dots ,G\left(k\right)$. It is called an $r$-factorization if every $G\left(i\right)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1\le i\le k$, $G\left(i\right)$ is a subgraph of $H\left(i\right)$.Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some 2-edge-connected $r$-factorization of $\mu K_m$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu >\lambda$ and either $m\ge 2n?1$, or $m=2n?2$ and $\mu =2$ and $\lambda =1$, or $n=3$ and $m=4$. We generalize their result to every $r\ge 2$ and $m\ge 2n?2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some 2-edge-connected $r$-factorization of $\mu K_m$ for every $r\ge 3$ and $m>(2?C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and $\mu$.     

A class of highly symmetric graphs,symmetric cylindrical constructions and their spectra

In this article, we introduce the algebra of block-symmetric cylinders and we show that symmetric cylindrical constructions on base-graphs admitting commutative decompositions behave as generalized tensor products. We compute the characteristic polynomial of such symmetric cylindrical constructions in terms of the spectra of the base-graph and the cylinders in a general setting. This gives rise to a simultaneous generalization of some well-known results on the spectra of a variety of graph amalgams, as various graph products, graph subdivisions and generalized Petersen graph constructions. While our main result introduces a connection between spectral graph theory and commutative decompositions of graphs, we focus on commutative cyclic decompositions of complete graphs and tree-cylinders along with a subtle group labeling of trees to introduce a class of highly symmetric graphs containing the Petersen and the Coxeter graphs. Also, using techniques based on recursive polynomials we compute the characteristic polynomials of these highly symmetric graphs as an application of our main result.     

On Eulerian orientations of even-degree hypercubes

It is well known that every Eulerian orientation of an Eulerian $2k$-edge connected (undirected) graph is strongly $k$-edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity. We show that every Eulerian orientation of the hypercube of degree $2k$ is strongly $k$-node connected.