The Complete Chromatic Number of Maximal Outerplane Graphs

Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of G.     

On（g,f）—Uniform Graphs

Thegraphsconsideredinthispaperwillbesimpleundirectedgraphs.LetGbeagraphwithvertexsetV(G)andedgesetE(G).ForavertexxofG,thedegreeofxinGisdenotedbydG(x).Theminimumdegreeandthemaximumdegree0fGaredenotedbyS(G)andb(G),respectively.Letgandfbetw0integer-valuedfunctionsdefined0nV(G)suchthatg(x)5f(x)foreveryx6V(G).Thena(g,f)-factorofGisaspanningsubgraphFofGsatisfyingg(x)SdF(x)5f(x)forallxEV(G).Ifg(x)=f(x)foreachxEV(G),thena(g,f)-factoriscalledanf-factor.Iffisaconstantfunctiontakingthevaluek,…     

Extreme Hexagonal Chainswith Respect to Two Partial Orders

LetG=(VE)beagraPh-AsubsetMofEiscalledatnatchinyinGifnotwoelementsofMareadjacentinG.AmatchingMiscalledani-matchingiflMl=i,andapethetmatchingifIMI=lVl/2.AsubsetI0fViscalledanindePendentvertexsetifnotwoelementsofIareadjacentinG.AnindependeDtvertexsetIiscalledani-indePendentvertexsetiflII=i.Denotebym(G)thenumber0fperfectmatchingsinG,byp(G)thenUInerofmatchingsinG(=theHosoyaindex),bya(G)thenUInerofindependentvertexsetsinG(=theMerrilield-Simm0nsindex)-Ahexagonalsystemisa2-connectedp1a…     

轮图的广义Mycielski图的邻强边色数

设图 G(V,E)为简单图 ,V(Mn(G) ) |{ v0 1,v0 2 ,… ,v0 p;v11,v12 ,… ,v1p,… ,vn1,vn2 ,… ,vnp}E(Mn(G) ) =E(G)∪ { vijv(i+ 1) k|v0 jv0 k ∈ E(G) ,1≤ j,k≤ p ,i =0 ,1,… ,n - 1}称 Mn(G)为 G的 n广义 Mycielski图 ,n为自然数 .本文得到了轮的广义 Mycielski图的临强边色数 .     

有限群特征标次数商的几点注记

对自然数n ,W(n)表示n中的素因子个数 (计重数 ) .对于有限群G的不可约复特征标集Irr(G) ,令W0 (G) =max{W(|G :kerχ|χ(1) ) | χ∈Irr(G) ,χ(1) >1} ,本文将考察W0 (G)≤ 3时有限群G的群论结构 .     

GRAPHS CHARACTERIZED BY LAPLACIAN EIGENVALUES

§1. Introduction Let G = (V,E) be a simple graph. The Laplacian matrix of G is L(G) = D(G)?A(G),where D(G) = diag (du,u ∈V (G)) (du is the degree of a vertex u) and A(G) are the degreediagonal and the adjacency matrices of G. The eigenvalues of L(G) are called the Laplacianeigenvalues and denoted by λ1(G) ≥λ2(G) ≥···≥λn(G) = 0or for short λ1 ≥λ2 ≥···≥λn = 0.The Laplacian matrix of a simple gra…     

Uniform convergence of the p-Bieberbach polynomials in domains with zero angles

Let G  C be a simply connected domain whose boundary L := αG is a Jordan curve and 0 ∈ G.Let w = ψ(z) be the conformal mapping of G onto the disk B(0, r0) := {w : |w| r0}, satisfying ψ(0) = 0,ψ′(0) = 1. We consider the following extremal problem for p 0:∫∫G|ψ′(z)- P ′n(z) pdσz→ min in the class of all polynomials Pn(z) of degree not exceeding n with Pn(0) = 0, P ′n(0) = 1. The solution to this extremal problem is called the p-Bieberbach polynomial of degree n for the pair(G, 0). We study the uniform convergence of the p-Bieberbach polynomials Bn,p(z) to the ψ(z) on G with interior and exterior zero angles determined depending on the properties of boundary arcs and the degree of their "touch".     

关于图D(Cn),C2n,C3n的星全色数

图G的一个k-全着色满足G的任何路长为2的点,边着色均不相同.我们称它为G的k-星全着色.图G的全部k-星全着色中最小的k称为图G的星全色数,记为Xn(G).讨论一些圈的星全染色问题,得到了图D(Cn)(n=0(mod 3)和n=0(mod 5)),C2n(n=0(mod 20)和n=0(mod 28))以及C3n(n=0(mod 28)和n=0(mod 36))的星全色数.     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

单圈图的无符号狄利克雷谱半径

Let G be a simple connected graph with pendant vertex set ?V and nonpendant vertex set V_0. The signless Laplacian matrix of G is denoted by Q(G). The signless Dirichlet eigenvalue is a real number λ such that there exists a function f ≠ 0 on V(G) such that Q(G)f(u) = λf(u) for u ∈ V_0 and f(u) = 0 for u ∈ ?V. The signless Dirichlet spectral radiusλ(G) is the largest signless Dirichlet eigenvalue. In this paper, the unicyclic graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with a given degree sequence are characterized.     

A POLYNOMIAL ALGORITHM FOR FINDING THE MINIMUM FEEDBACK VERTEX SET OF A 3-REGULAR SIMPLE GRAPH 1

A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.     

一个求外平面图最小顶点赋权反馈点集的线性时间算法

若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法.     

A POLYNOMIAL ALGORITHM FOR FINDING THE MINIMUM FEEDBACKVERTEX SET OF A 3-REGULAR SIMPLE GRAPHR1

A subset of the vertex set of a graph is a feedback vertex set of thegraph if the resulting graph is a forest after removed the vertexsubset from the graph. A polynomial algorithm for finding a minimumfeedback vertex set of a 3-regular simple graph is provided.     

A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs

A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in seriesparallel graphs and present a linear-time exact algorithm to solve it.     

A class of planar four-colorable graphs

A sufficient condition is given for a planar graph to be 4-colorable. This condition is in terms of the sums of the degrees of a subset of the vertex set of the graph.     

Total restrained bondage in graphs

A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V (G) S is also adjacent to a vertex in V (G) S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.     

上连通和超连通的三次Bi-Cayley图

Let G be a finite group and let S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G×{0, 1} and edge set {(g, 0) (sg, 1) : g∈G, s ∈ S}. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if every minimum vertex cut creates two components, one of which is an isolated vertex. In this paper, super-connected and/or hyper-connected cubic Bi-Cayley graphs are characterized.     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.     

5-正则图的全控制数的一个注记

设G是不含孤立点的图,S是G的一个顶点子集,若G的每一个顶点都与S中的某顶点邻接,则称S是G的全控制集.G的最小全控制集所含顶点的个数称为G的全控制数,记为γt(G).Thomasse和Yeo证明了若G是最小度至少为5的n阶连通图,则γt(G)≤17n/44.在5-正则图上改进了Thomasse和Yeo的结论,证明了若G是n阶5-正则图,则,γt(G)≤106n/275.