Flow number and circular flow number of signed cubic graphs

Let $\mathrm{\Phi }(G,\sigma )$ and ${\mathrm{\Phi }}_c(G,\sigma )$ denote the flow number and the circular flow number of a flow-admissible signed graph $(G,\sigma )$, respectively. It is known that $\mathrm{\Phi }(G)=?{\mathrm{\Phi }}_c(G)?$ for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that $\mathrm{\Phi }(G,\sigma )?{\mathrm{\Phi }}_c(G,\sigma )<1$ holds also for every flow-admissible signed graph $(G,\sigma )$. This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory. For cubic graphs we show that $\mathrm{\Phi }(G,\sigma )=3$ if and only if ${\mathrm{\Phi }}_c(G,\sigma )=3$ and if $\mathrm{\Phi }(G,\sigma )\in \{4,5\}$, then $4\le {\mathrm{\Phi }}_c(G,\sigma )\le \mathrm{\Phi }(G,\sigma )$. We also prove that all pairs of flow number and circular flow number that fulfil these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless signed cubic graphs. Finally, we prove that all currently known flow-admissible graphs without nowhere-zero 5-flow have flow number and circular flow number 6 and propose several conjectures in this area.     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

The graph Ramsey number R(Fℓ,K6)

For a given pair of two graphs $(F,H)$, let $R(F,H)$ be the smallest positive integer $r$ such that for any graph $G$ of order $r$, either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. Baskoro, Broersma and Surahmat (2005) conjectured that $R(F_{\ell },K_n)=2\ell (n-1)+1$for $\ell \ge n\ge 3$, where $F_{\ell }$ is the join $K_1+\ell K_2$ of $K_1$ and $\ell K_2$. In this paper, we prove that this conjecture is true for the case $n=6$.     

关于图的子着色

本文主要讨论了子色唯一图的结构，并给出了唯一k-子色图、最大子色图的边临界子色图的特征．     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C，如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G），Vj′∈V（G′）且vivj∈E（G））那么，称D（C）是C的倍图，如果V（D（G））=V（C）∪V（G′），E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G），vj′∈V（G’）and vivj∈（G）），称D（C）是G的补倍图，这里G′是G的拷贝．本文研究了D（G）和D的色数，边色数，欧拉性，哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

Ramsey数R_m(3)的计算及Schur数的新上界

利用抽屉原理,给出了Ramsey数Rm(3)的一个递推公式,得到Rm(3)准确值计算的一个具体表达式,并利用Rm(3)的计算公式给出了Schur数的一个新的上界。     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The competition numbers of complete tripartite graphs

For a graph G, it is known to be a hard problem to compute the competition number k(G) of the graph G in general. In this paper, we give an explicit formula for the competition numbers of complete tripartite graphs.     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation     

若干图的广义Mycielski图的边色数

设图G(V,E)为简单图,V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp}EMn(G))=E(G)∪vijv(i+1)kv0 jv0k∈E(G),1 j,k p,i=0,1,…,n-1称Mn(G)为G的n串广义M ycielsk i图,其中n为自然数,V(G)={v01,v02,…,v0p}.本文得到了路、圈、扇、轮、星图的广义M ycielsk i图的边色数.     

The crossing number of K11 is 100

The crossing number of K_n is known for n ? 10. We develop several simple counting properties that we shall exploit in showing by computer that cr(K₁₁ = 100, which implies that cr(K₁₂) = 150. We also determine the numbers of non‐isomorphic optimal drawings of K₉ and K₁₀. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 128–134, 2007     

Circular flow on signed graphs

The circular flow number Φc(G,σ) of a signed graph (G,σ) is the minimum r for which an orientation of (G,σ) admits a circular r-flow. We prove that the circular flow number of a signed graph (G,σ) is equal to the minimum imbalance ratio of an orientation of (G,σ). We then use this result to prove that if G is 4-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) (as well as Φ(G,σ)) is at most 4. If G is 6-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) is strictly less than 4.     

Roman domination in regular graphs

A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑_u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γ_R(G)≤2γ(G) and defined a graph G to be Roman if γ_R(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P_3k,P_3k+2,C_3k,C_3k+2 for k≥1, K_m,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs.     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009     

匹配数与控制数相等的图的结构性质

我们分别用γ(G)，β(G)和α(G)表示图G的控制数、匹配数和覆盖数，对任意连通图，有γ(G)≤β(G)≤α(G)成立，1998年，Randerath和Volkmann给出了控制数等于覆盖数的图的特征，本文首先证明了匹配数与控制数相等的图其最小度不超过2，而后给出了最小度为2的图的结构性质。     

On the Crossing Number of without Computer Assistance

We present several general results about drawings of , as a beginning to trying to determine its crossing number. As application, we give a complete proof that the crossing number of K₉ is 36 and that all drawings in one large, natural class of drawings of K₁₁ have at least 100 crossings.