Longest Cycles in 3-connected Graphs with Given Independence Number

Fouquet and Jolivet conjectured that a k-connected graph of order n and independence number α ≥ k has a cycle of length at least [Fouquet and Jolivet, Problèmes combinatoires et théorie des graphes Orsay (1976), Problems, page 438]. Here we prove this conjecture for k=3.     

Nowhere-Zero 5-Flows and Even (1,2)-Factors

A graph G = (V, E) admits a nowhere-zero k-flow if there exists an orientation H = (V, A) of G and an integer flow ${\varphi:A \to \mathbb{Z}}$ such that for all ${a \in A, 0 < |\varphi(a)| < k}$ . Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set ${F \subseteq E}$ such that the degree of any vertex v in the subgraph induced by F is 1 or 2. Let us call an edge of G, F-balanced if either it belongs to F or both its ends have the same degree in F. Call a cycle of G F-even if it has an even number of F-balanced edges. A (1,2)-factor F of G is even if each cycle of G is F-even. The main result of the paper is that a cubic graph G admits a nowhere-zero 5-flow if and only if G has an even (1,2)-factor.     

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.     

Lower Bounds of Size Ramsey Number for Graphs with Small Independence Number

Acta Mathematicae Applicatae Sinica, English Series - Let r ≥ 3 be an integer such that r ? 2 is a prime power and let H be a connected graph on n vertices with average degree at least...     

Nowhere-Zero 4-Flows,Simultaneous Edge-Colorings,And Critical Partial Latin Squares

It is proved in this paper that every bipartite graphic sequence with the minimum degree 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares.* Partially supported by RGC grant HKU7054/03P. Partially supported by the National Security Agency under Grants MDA904-00-1-00614 and MDA904-01-1-0022.     

Bounds for the Independence Number of Critical Graphs

In 1968 Vizing conjectured that any independent vertex set ofan edge-chromatic critical graph G contains at most half ofthe vertices of G, that is, (G|(G)|). Let be the maximum vertexdegree in a critical graph. For each , we determine c() suchthat (G)c()|V)|. 1991 Mathematics Subject Classification 05C15,05C70.     

图的字典积的非零整数流(英文)

充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流.     

Symmetrical Independence Tests for Two Random Vectors with Arbitrary Dimensional Graphs

Test of independence between random vectors X and Y is an essential task in statistical inference.One type of testing methods is based on the minimal spanning t...     

A Characterization of Graphs Where the Independence Number Equals the Radius

In a classical 1986 paper by Erdös, Saks and Saós every graph of radius r has an induced path of order at least 2r ? 1. This result implies that the independence number of such graphs is at least r. In this paper, we use a result of S. Fajtlowicz about radius-critical graphs to characterize graphs where the independence number is equal to the radius, for all possible values of the radius except 2, 3, and 4. We briefly discuss these remaining cases as well.     

An Asymptotic Independence Theorem for the Number of Matchings in Graphs

Let z(G) be the number of matchings (independent edge subsets) of a graph G. For a set M of edges and/or vertices, the ratio represents the probability that a randomly picked matching of G does not contain an edge or cover a vertex that is an element of M. We provide estimates for the quotient , depending on the sizes of the disjoint sets A and B, their distance and the maximum degree of the underlying graph G. It turns out that this ratio approaches 1 as the distance of A and B tends to ∞, provided that the size of A and B and the maximum degree are bounded, showing asymptotic independence. We also provide an application of this theorem to an asymptotic enumeration problem related to the dimer-monomer model from statistical physics. This material is based upon work supported by the German Research Foundation DFG under grant number 445 SUA-113/25/0-1 and the South African National Research Foundation under grant number 65972.     

匹配数为2的图的最小特征值

在所有给定阶数且匹配数为2的连通图中,我们刻画了最小特征值达到极小的图,给出了这类图最小特征值的下界.     

两类图的逆符号边控制数

研究了图G的逆符号边控制数■.利用穷标法及分类讨论法,主要得到了两类图n·C_m和n-C_m逆符号边控制数的精确值,从而推广了已知结果.这里C_m表示长为m的圈,n·C_m和n-C_m分别表示恰有一个公共点和有一条公共边的n个圈的拷贝.     

含有两个非临界点的强连通定向图的弧数

证明顶点数为$n\geq 4$,弧数为$m\geq {n-1 \choose 2}+3$的强连通定向
图$D$中存在两点$u^*$、!$v^*$,使得$D-u^*$和$D-v^*$都是强连通的, 并用例子说明这里所给的
关于弧数的下界是紧的.     

Thickness-Two Graphs Part Two: More New Nine-Critical Graphs,Independence Ratio,Cloned Planar Graphs,and Singly and Doubly Outerplanar Graphs

There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work in [4]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs, and we give upper and lower bounds for the largest chromatic number of the former two classes.     

A New Lower Bound on the Potential-Ramsey Number of Two Graphs

A nonincreasing sequence π=(d₁,…,d_n) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.In this case,G is referred to as a realization of π.Given a graph H,a graphic sequence π is potentially H-graphic if π has a realization containing H as a subgraph.For graphs G₁ and G₂,the potential-Ramsey number r_pot(G₁,G₂) is the smallest integer k such that for every k-term graphic ...     

Independence Numbers of Planar Contact Graphs

   Abstract. We show that for a large class of convex discs C (including strictly convex discs), there exists an ε=ε(C)>0 such that the independence number of the contact graph of any packing of n translates of C in the plane is at least (1/4 + ε)n . For C a circle, we improve the lower bound of Csizmadia to 8/31n .     

Independence Numbers of Planar Contact Graphs

Abstract. We show that for a large class of convex discs C (including strictly convex discs), there exists an ε=ε(C)>0 such that the independence number of the contact graph of any packing of n translates of C in the plane is at least (1/4 + ε)n . For C a circle, we improve the lower bound of Csizmadia to 8/31n .     

交叉数为2且因子图为路的笛卡尔积图

M.Kle??和J.Petrillová刻画了当G1为圈且cr (G1G2)=2时,因子图G1和G2所满足的充要条件.在此基础上,该文进一步刻画了在cr (G1G2)=2的前提下,当G1=P4,或者G1=P3且△(G2)=4时,因子图G2应满足的充要条件.