GRAPHS WHOSE CIRCULAR CLIQUE NUMBER EQUAL THE CLIQUE NUMBER

The circular clique number of a graph G is the maximum fractional k/d such that G^kd admits a homomorphism to G. In this paper, we give some sufficient conditions for graphs whose circular clique number equal the clique number, we also characterize the K1,3-free graphs and planar graphs with the desired property.     

(4m, m)-CHOOSABILITY OF PLANE GRAPHS

1 IntroductionAll graphs considered in tabs paper are abate and sable. Undecked notations and termalnologies can be found in [if.Let G = (V, E,F) be a plase graph, where V, E and F denote the s6t of venices, edgesand faces of G, respectively. We use NG(v) and dG(v) to denote the set and nUmber of venicesadjacent to a vertex yi respectively, and use 6(G) to denote the inininuun degree of G. A vertexv is called a k-vertex if v has degree k. A face of a plane graph is said to be incident w…     

SOME RESULTS ON CIRCULAR PERFECT GRAPHS AND PERFECT GRAPHS

An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.     

MINIMALLY （n, λ）-CONNECTED GRAPHS OF LOW ORDER AND MAXIMAL SIZE＊

A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n which is obtained from the complete bipartite graph Kn,p-n by replacing each edge with A multiple edges; if 3n - 1 ≥ ｜G}≥ n ＋ 1, then e（G） ≤λ（｜G｜ ＋ n）^2/8. In this paper, we determine all the minimally （n, λ）-connected graphs with order p and the maximum size λ（p＋n）^2/8 for 3n- 1 ≥ p ≥ n＋ 1 for 3n-1≥p≥n＋1.     

VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k 1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.     

THE LINEAR ARBORICITY 0F COMPOSITl0N GRAPHS

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G.Akiyama,Exoo and Harary conjectured that la(G)=[Δ（G） 1/2] for any regular graph G.In this papedr,we prove the conjecture for some composition graphs,in particular,forcomplets multipartite graphs.     

A NOTE ON CONNECTED FACTORS IN CLAW-FREE GRAPHS

1. IntroductionAll graphs considered here are finite and undirected, without loops or multiple edges. Thevertex set, edge set and the degree of a vertex v of a graph G are denoted, respectively, byV(G),E(G) and dG(v). For a set S G V(G) the subgraph of G induced by S is denoted byG[S].Let G be a graph, j and g positive integer Valued functions on V(G) with f(v) S g(v) 5dG(u) for all v 6 V(G). A spanmng SUbgraph F Of G is called an [f,g]-factor Of G if forall v E V(G), f(v) 5 dF(v…     

An Upper Bound for the Cubicity of Folded Hypercube

For a graph, its boxicity is the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes＇in the k-dimension space. When the boxes are restricted to be axis-parallel k-dimension cube＇s, the minimum k required to represent G is called the cubicity of G. In this paper, a special graph .called unit-interval graph. IG[X, Y] is given, then 2n such graphs which have the same vertices as V（FQn） are constructed, where FQ, is the n-dimension folded hypercube. Thanks to the specia] structure of IG[X, Y], the result that cubicity（FQn）≤ 2n is proved.     

On the Merrifield-Simmons Indices and Hosoya Indices of Cyclic Graphs

The Merrifield-Simmons index and Hosoya index are defined as the number of the graph G（V, E） as the number of subsets of V（G） in which no tow vertices are adjacent and the number of subsets of E（G） in which no two edges are incident, respectively. In this paper, we characterize the Unicyclic graphs with Merrifield-Simmons indices and Hosoya indices, respectively. And double-cyclic graphs with Hosoya indices among the doublecyclic graphs with n vertices.     

FORBIDDEN SUBGRAPHS,DEGREES,NEIGHBORHOOD UNIONS AND CIRCUMFERENCES OF GRAPHS

Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:(1) Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgraphL of order four of G(?)|V_1(L)∩S_c|≥2 if L≌K_(1,3),and |V(L)∩S_c|≥1 if L≌P_4,then thecircumference of G is at least c,where V_1(L)is the set of vertices with degree 1 of L,S_c isthe set of vertices with degree at least c/2 of G and P_4 is a path of order 4.(2) Let G be a 2-connected graph of order n,and n≥s+2.If for each induced subgraphL of G isomorphic to K_(1,3)or P_4,d_L(u,v)=2(?)|N(u)∪N(v)|≥s,then the circumferencec (G) of G is at least s+2.Moreover,if n≥s+3 and s is odd,then c(G)≥s+3.     

Removable ears of 1-extendable graphs

<正> Carvalho,Lucchesi and Murty proved that any 1-extendable graph G different from K_2and C_(2n)has at least Δ(G)edge-disjoint removable ears,and any brick G distinct from K_4 and■hasat least Δ(G)-2 removable edges,where Δ(G)denotes the maximum degree of G.In this paper,weimprove the lower bounds for numbers of removable ears and removable edges of 1-extendable graphs.It is proved that any 1-extendable graph G different from K_2 and C_(2n)has at least χ′(G)edge-disjointremovable ears,and any brick G distinct from K_4 and■has at least χ′(G)-2 removable edges,whereχ′(G)denotes the edge-chromatic number of G.     

Induced Subgraph in Random Regular Graph

Let Gn,d be a random d-regular graph with n vertices, where d = o（n）. Given a fixed graph H, YH denotes the number of induced copies of H in Gn d In this paper, the authors determine the threshold of the event ＂YH 〉 0＂, and also obtain the induced subgraph counts inside the threshold interval.     

RELIABILITY OF LINEAR （n,f, k） SYSTEMS WITH WEIGHTED COMPONENTS

The (n, f, k): F(G) system consists of n components and the system fails (works) if and only if there are at least f failed (working) components or at least k consecutive failed (working) components. These system models can be used in electronic equipment, automatic payment systems in banks, and furnace systems. In this paper we introduce and study the (n, f, k):F and (n, f, k): G systems consisting of weighted components. Recursive equations are presented for reliability evaluation of these new models. We also provide some conditions on the weights to represent weighted-(n, f, k) systems as usual (n, f, k) systems.     

Transient Queue Size Distribution Solution of Geom / G / 1 Queue with Feedback-A Recursive Method

This paper considers the Geom / G / 1 queueing model with feedback according to a late arrival system with delayed access (LASDA). Using recursive method, this paper studies the transient property of the queue size from the initial state N(0⁺) = i. Some new results about the recursive expression of the transient queue size distribution at any epoch n ⁺ and the recursive formulae of the equilibrium distribution are obtained. Furthermore, the recursive formulae of the equilibrium queue size distribution at epoch n ⁻, and n are obtained, too. The important relations between stationary queue size distributions at different epochs are discovered (being different from the relations given in M / G / 1 queueing system). The model discussed in this paper can be widely applied in all kinds of communications and computer network. This research is supported by the National Natural Science Foundation of China under Grant No. 70871084, the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No. 200806360001, and the Scientific Research Fund of Southwestern University of Finance and Economics.     

A NEW FAMILY OF TRIVALENT CAYLEY NETWORKS ON WREATH PRODUCT Zm ～ Sn

We propose a new family of interconnection networks （WGn^m） with regular degree three. When the generator set is chosen properly, they are isomorphic to Cayley graphs on the wreath product Zm ～ Sn. In the case of m ≥ 3 and n ≥3, we investigate their different algebraic properties and give a routing algorithm with the diameter upper bounded by [m/2]（3n^2- 8n ＋ 4） - 2n ＋ 1. The connectivity and the optimal fault tolerance of the proposed networks are also derived. In conclusion, we present comparisons of some familiar networks with constant degree 3.     

Star Chromatic Numbers of Planar Graphs

１ＩｎｔｒｏｄｕｃｔｉｏｎＤｅｆｉｎｉｔｉｏｎ１．１Ｌｅｔｋ,ｄｂｅｎａｔｕｒａｌｎｕｍｂｅｒｓｓｕｃｈｔｈａｔｋ２ｄ,ａ（ｋ,ｄ）－ｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈＧ＝（Ｖ,Ｅ）ｉｓａｍａｐｐｉｎｇｃ：Ｖ→Ｚｋ,ｓｕｃｈｔｈａｔｆｏｒｅａｃｈｅｄ...     

On the Tractability of Shortest Path Problems in Weighted Edge-Coloured Graphs

A weighted edge-coloured graph is a graph for which each edge is assigned both a positive weight and a discrete colour, and can be used to model transportation and computer networks in which there are multiple transportation modes. In such a graph paths are compared by their total weight in each colour, resulting in a Pareto set of minimal paths from one vertex to another. This paper will give a tight upper bound on the cardinality of a minimal set of paths for any weighted edge-coloured graph. Additionally, a bound is presented on the expected number of minimal paths in weighted edge–bicoloured graphs. These bounds indicate that despite weighted edge-coloured graphs are theoretically intractable, amenability to computation is typically found in practice.     

Discriminant analysis based on statistical depth

<正> In the past two decades,many statistical depth functions seemed as powerful exploratoryand inferential tools for multivariate data analysis have been presented.In this paper,a new depthfunction family that meets four properties mentioned in Zuo and Serfling(2000)is proposed.Then aclassification rule based on the depth function family is proposed.The classification parameter b couldbe modified according to the type-Ⅰ error α,and the estimator of b has the consistency and achievesthe convergence rate n~(-1/2).With the help of the proper selection for depth family parameter c,theapproach for discriminant analysis could minimize the type-Ⅱ error β.A simulation study and a realdata example compare the performance of the different discriminant methods.     

Forbidden Subgraphs, Distance,and Hamiltonicity

ＦｏｒｂｉｄｄｅｎＳｕｂｇｒａｐｈｓ，Ｄｉｓｔａｎｃｅ，ａｎｄＨａｍｉｌｔｏｎｉｃｉｔｙＨＵＺｈｉｑｕａｎＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＨｕａｚｈｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００７０Ａｂｓｔｒａｃｔ：Ａｇｒ...