关于图值随机元序列的强极限定理

本文研究在局部连通图中取值的随机元的r-阶均值集、r-阶广义样本均值集的基本性质及其极限性质.利用关于随机元的分离引理以及随机游动的常返性,得到了关于图值随机元序列广义强大数定理.推广了已有的结果.     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

On the Existence of Elementary Abelian Cycle Systems

We present some necessary and/or sufficient conditions for the existence of an elementary abelian cycle system of the complete graph. We propose a construction for some classes of perfect elementary abelian cycle systems. Finally we consider elementary abelian k-cycle systems of the complete multipartite graph.      

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Vertices of Degree 5 in a Contraction Critically 5-connected Graph

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.     

On the <Emphasis Type="Italic">K</Emphasis>-Theory of Graph <Emphasis Type="Italic">C</Emphasis><Superscript>*</Superscript>-Algebras

We classify graph C ^*-algebras, namely, Cuntz-Krieger algebras associated to the Bass-Hashimoto edge incidence operator of a finite graph, up to strict isomorphism. This is done by a purely graph theoretical calculation of the K-theory of the C ^*-algebras and the method also provides an independent proof of the classification up to Morita equivalence and stable equivalence of such algebras, without using the boundary operator algebra. A direct relation is given between the K ₁-group of the algebra and the cycle space of the graph. We thank Jakub Byszewski for his input in Sect. 2.8. The position of the unit in K ₀( _Ч) was guessed based on some example calculations by Jannis Visser in his SCI 291 Science Laboratory at Utrecht University College.     

The expected value models on Sugeno measure space

Uncertain programming is a theoretical tool to handle optimization problems under uncertain environment. The research reported so far is mainly concerned with probability, possibility, or credibility measure spaces. Up to now, uncertain programming realized in Sugeno measure space has not been investigated. The first type of uncertain programming considered in this study and referred to as an expected value model optimizes a given expected objective function subject to some expected constraints. We start with a concept of the Sugeno measure space. We revisit some main properties of the Sugeno measure and elaborate on the g_λ random variable and its characterization. Furthermore, the laws of the large numbers are discussed based on this space. In the sequel we introduce a Sugeno expected value model (SEVM). In order to construct an approximate solution to the complex SEVM, the ideas of a Sugeno random number generation and a Sugeno simulation are presented along with a hybrid approach.     

On connected factors inK 1,3-free graphs

A graph is said to beK _1,3-free if it contains noK _1,3 as an induced subgraph. It is shown in this paper that every 2-connectedK _1,3-free graph contains a connected [2,3]-factor. We also obtain that every connectedK _1,3-free graph has a spanning tree with maximum degree at most 3. This research is partially supported by the National Natural Sciences Foundation of China and by the Natural Sciences Foundation of Shandong Province of China.     

Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

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 the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we proved that a vertex transitive bipartite graph is not super-connected if and only if it is isomorphic to the lexicographic product of a cycle C_n(n ≥ 6) by a null graph N_m. We also characterized non-hyper-connected vertex transitive bipartite graphs.     

Clearing Models for M/G/1 Queues

We consider M/G/1-type queueing systems with disasters, occurring at certain random times and causing an instantaneous removal of the entire residual workload from the system. After such a clearing, the system is assumed to be ready to start working again immediately. We consider clearings at deterministic equidistant times, at random times and at crossings of some prespecified level, and derive the stationary distribution of the workload process for these clearing times and some of their combinations.     

Limit Theorems for Non-Commutative Random Variables

We study the weak law of large numbers and the central limit theorem for non-commutative random variables. We first define the concepts of variance and expectation for probability measures on homogeneous spaces, and formulate the weak law of large numbers and the central limit theorem for probability measures on locally compact groups. Then, we consider the non-commutative case, where the homogeneous space is replaced by a C^*-algebra that is equipped with a locally compact group G of automorphisms. We define the concepts of variance and expectation in the non-commutative situation. Furthermore, we prove that the weak law of large numbers and the central limit theorem hold for non-commutative random variables on if they hold on the group G of automorphisms.     

E -Theoretic Duality for Higher Rank Graph Algebras

We prove that there is a Poincaré type duality in E-theory between higher rank graph algebras associated with a higher rank graph and its opposite correspondent. We obtain an r-duality, that is the fundamental classes are in E^r. The basic tools are a higher rank Fock space and higher rank Toeplitz algebra which has a more interesting ideal structure than in the rank 1 case. The K-homology fundamental class is given by an r-fold exact sequence whereas the K-theory fundamental class is given by a homomorphism. The E-theoretic products are essentially pull-backs so that the computation is done at the level of exact sequences. Mathematics Subject Classification (2000): 46L80.     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

Classification of extensions of classifiable -algebras

For a certain class of extensions of C^*-algebras in which B and A belong to classifiable classes of C^*-algebras, we show that the functor which sends to its associated six term exact sequence in K-theory and the positive cones of K₀(B) and K₀(A) is a classification functor. We give two independent applications addressing the classification of a class of C^*-algebras arising from substitutional shift spaces on one hand and of graph algebras on the other. The former application leads to the answer of a question of Carlsen and the first named author concerning the completeness of stabilized Matsumoto algebras as an invariant of flow equivalence. The latter leads to the first classification result for nonsimple graph C^*-algebras.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

A decomposition approach for a very large scale optimal diversity management problem

This paper focuses on the solution of the optimal diversity management problem formulated as a p-Median problem. The problem is solved for very large scale real instances arising in the car industry and defined on a graph with several tens of thousands of nodes and with several millions of arcs. The particularity is that the graph can consist of several non connected components. This property is used to decompose the problem into a series of p-Median subproblems of a smaller dimension. We use a greedy heuristic and a Lagrangian heuristic for each subproblem. The solution of the whole problem is obtained by solving a suitable assignment problem using a Branch-and-Bound algorithm.Received: June 2004 / Revised version: December 2004MSC classification: 49M29, 90C06, 90C27, 90C60All correspondence to: Antonio SforzaIgor Vasilev: Support for this author was provided by NATO grant CBP.NR.RIG.911258.     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.     

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.