图的联结数与分数κ-消去图

设G是一个图,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.若k=2,则称分数k-消去图为分数2-消去图.本文证明了当bind（G）≥2,并且δ（G）≥3时,G是分数2-消去图.     

关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G, 如果对于V(G)的任意k元子集S, 子图G-S都包含分数完美匹配, 那么称G为分数k-因子临界图. 如果图G的每个k-匹配M都包含在一个分数完美匹配中, 那么称图G为分数k-可扩图. 给出一个图是分数k-因子临界图和分数k-可扩图的充分条件, 并给出一个图是分数k-因子临界图的充分必要条件.     

Independence number and minimum degree for fractional ID-k-factor-critical graphs

Let k be an integer with k?≥?1, and let G be a graph. A k-factor of G is a spanning subgraph F of G such that d _F (x)?=?k for each ${x\in V(G)}$ . Let ${h:E(G)\rightarrow[0,1]}$ be a function. If ${\sum_{e\ni x}h(e)=k}$ holds for each ${x\in V(G)}$ , then we call G[F _h ] a fractional k-factor of G with indicator function h, where ${F_h=\{e\in E(G): h(e) >0 \}}$ . A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical) if G?I has a fractional k-factor for every independent set I of G. In this paper, we prove that if ${\alpha(G)\leq\frac{4k(\delta(G)-k+1)}{k^{2}+6k+1}}$ , then G is fractional ID-k-factor-critical. The result is best possible in some sense.     

The Ramsey numbers for disjoint unions of graphs

For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kS_n,W_m)=R(S_n,W_m)+(k-1)n. Furthermore, if |G_i|>(|G_i|-|G_i+1|)(χ(H)-1) and R(G_i,H)=(χ(H)-1)(|G_i|-1)+1, for each i, then .     

On the edge-binding number of some plane graphs

1. IntroductionSince WOodall gave out the concept of biIldi11g Ilu1lJber in 1973[l] ! the bil1ding nunlber fOrsome specia1 classes have beeIl studied by Kane and WaIlg Jianfang[']. Mirolawa Skowronskahave studied the binding number of Halin-graph[']. ZI1ang Zhongfu, Liu Li1lzhong andZhang Jianxun have extended the bil1di11g nuInber to the edges and studied tlle edge-bindingnumber of path, cycle, coInplete grapl1. I1l this paper, we study the edge-binding number ofouter plane graph, Ha…     

Fractional chromatic numbers of cones over graphs

We introduce a construction called the cone over a graph. It is a natural generalisation of Mycielski's construction. We give a formula for the fractional chromatic numbers of all cones over graphs, which generalizes that given in 3 for Mycielski's construction. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 87–94, 2001     

Sum choice numbers of some graphs

Let f be a function assigning list sizes to the vertices of a graph G. The sum choice number of G is the minimum ∑_v∈V(G)f(v) such that for every assignment of lists to the vertices of G, with list sizes given by f, there exists proper coloring of G from the lists. We answer a few questions raised in a paper of Berliner, Bostelmann, Brualdi, and Deaett. Namely, we determine the sum choice number of the Petersen graph, the cartesian product of paths , and the complete bipartite graph K_3,n.     

Estimates of the number of independent sets in graphs with a fixed independence number

Attainable estimates of the number of independent sets in graphs with a given size of the maximal independent set are obtained. Three graph classes—trees, forests, and the class of all graphs—are considered. Extremal graphs are described.     

Distinguishing chromatic numbers of complements of Cartesian products of complete graphs

The distinguishing chromatic number of a graph, $G$, is the minimum number of colours required to properly colour the vertices of $G$ so that the only automorphism of $G$ that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klav?ar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large.     

Proof of a conjecture on fractional Ramsey numbers

Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function r_f (a₁, a₂, …, a_k) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164–178, 2010     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

无爪图上团横贯数的界

设 G=(V,E) 为简单图,图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交,即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目,记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.     

Graph pegging numbers

In graph pegging, we view each vertex of a graph as a hole into which a peg can be placed, with checker-like “pegging moves” allowed. Motivated by well-studied questions in graph pebbling, we introduce two pegging quantities. The pegging number (respectively, the optimal pegging number) of a graph is the minimum number of pegs such that for every (respectively, some) distribution of that many pegs on the graph, any vertex can be reached by a sequence of pegging moves. We prove several basic properties of pegging and analyze the pegging number and optimal pegging number of several classes of graphs, including paths, cycles, products with complete graphs, hypercubes, and graphs of small diameter.