Two-ended regular median graphs

We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends.For cubic median graphs G the condition of linear growth can be weakened to the condition that G has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.     

图的因子和因子分解的若干进展

本文综述了图的的因子和因子分解近年来的一些新结果。主要有图的因子与各种参数之间的关系,图有某种因子的一些充分必要条件,特别是图有ｋ－因子的一些充分条件以及关于图的因子分解和正交因子分解的一些新结果。文中提出了一些新的问题和猜想。     

Cyclic orthogonal double covers of 4-regular circulant graphs

An orthogonal double cover (ODC) of a graph H is a collection G={G_v:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members G_u and G_v in G, |E(G_u)∩E(G_v)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs.     

Partial characterizations of coordinated graphs: line graphs and complements of forests

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The list of minimal forbidden induced subgraphs for the class of coordinated graphs is not known. In this paper, we present a partial result in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or the complement of a forest. F. Bonomo, F. Soulignac, and G. Sueiro’s research partially supported by UBACyT Grant X184 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). The research of G. Durán is partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

Edge-coloring of multigraphs

We introduce a monotone invariant π(G) on graphs and show that it is an upper bound of the chromatic index of graphs. Moreover, there exist polynomial time algorithms for computing π(G) and for coloring edges of a multigraph G by π(G) colors. This generalizes the classical edge-coloring theorems of Shannon and Vizing.     

Free groups and ends of graphs

Let X be a connected graph. An automorphism of X is said to be parabolic if it leaves no finite subset of vertices in X invariant and fixes precisely one end of X and hyperbolic if it leaves no finite subset of vertices in X invariant and fixes precisely two ends of X. Various questions concerning dynamics of parabolic and hyperbolic automorphisms are discussed.The set of ends which are fixed by some hyperbolic element of a group G acting on X is denoted by ?(G). If G contains a hyperbolic automorphism of X and G fixes no end of X, then G contains a free subgroup F such that ?(F) is dense in ?(G) with respect to the natural topology on the ends of X.As an application we obtain the following: A group which acts transitively on a connected graph and fixes no end has a free subgroup whose directions are dense in the end boundary.     

Decomposing Graphs into Long Paths

It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C ₃, C ₄, C ₅, and K ₄−e have no such decompositions. We construct an infinite sequence {F _i } _i=0 ^∞ of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition. This revised version was published online in June 2006 with corrections to the Cover Date.     

Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000     

Balanced and 1-balanced graph constructions

There are several density functions for graphs which have found use in various applications. In this paper, we examine two of them, the first being given by b(G)=|E(G)|/|V(G)|, and the other being given by g(G)=|E(G)|/(|V(G)|−ω(G)), where ω(G) denotes the number of components of G. Graphs for which b(H)≤b(G) for all subgraphs H of G are called balanced graphs, and graphs for which g(H)≤g(G) for all subgraphs H of G are called 1-balanced graphs (also sometimes called strongly balanced or uniformly dense in the literature). Although the functions b and g are very similar, they distinguish classes of graphs sufficiently differently that b(G) is useful in studying random graphs, g(G) has been useful in designing networks with reduced vulnerability to attack and in studying the World Wide Web, and a similar function is useful in the study of rigidity. First we give a new characterization of balanced graphs. Then we introduce a graph construction which generalizes the Cartesian product of graphs to produce what we call a generalized Cartesian product. We show that generalized Cartesian product derived from a tree and 1-balanced graphs are 1-balanced, and we use this to prove that the generalized Cartesian products derived from 1-balanced graphs are 1-balanced.     

The galaxies of nonstandard enlargements of infinite and transfinite graphs

The galaxies of the nonstandard enlargements of connected, conventionally infinite graphs as well as of walk-connected transfinite graphs are defined, analyzed, and illustrated by some examples. It is then shown that any such enlargement either has exactly one galaxy, its principal one, or it has infinitely many galaxies. In the latter case, the galaxies are partially ordered by their “closeness” to the principal galaxy. If an enlargement has a galaxy Γ different from its principal galaxy, then it has a two-way infinite sequence of galaxies that contains Γ and is totally ordered according to that “closeness” property. There may be many such totally ordered sequences.Furthermore, a walk-connected graph G¹ of transfinite rank 1 consists in general of connected conventional graphs (graphs of rank 0, called 0-sections) that are walk-connected together at their infinite extremities. The enlargement of G¹ consists of the enlargement of G¹, as well as of the enlargements of its 0-sections. The latter enlargements are all contained within the principal galaxy of . Moreover, may have other galaxies of rank 1; these too are partially and totally ordered as before. These results extend to the enlargements of transfinite graphs of ranks greater than 1.     

Developments on spectral characterizations of graphs

In [E.R. van Dam, W.H. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl. 373 (2003), 241-272] we gave a survey of answers to the question of which graphs are determined by the spectrum of some matrix associated to the graph. In particular, the usual adjacency matrix and the Laplacian matrix were addressed. Furthermore, we formulated some research questions on the topic. In the meantime, some of these questions have been (partially) answered. In the present paper we give a survey of these and other developments.     

Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors

A hereditary property of graphs is any class of graphs closed under isomorphism and subgraphs. Let 𝒫₁, 𝒫₂,…, 𝒫_n be hereditary properties of graphs. We say that a graph G has property 𝒫_1°𝒫_2°···_°𝒫_n if the vertex set of G can be partitioned into n sets V₁, V₂,…, V_n such that the subgraph of G induced by V_i belongs to 𝒫_i; i = 1, 2,…, n. A hereditary property is said to be reducible if there exist hereditary properties 𝒫₁ and 𝒫₂ such that ℛ = 𝒫_1°𝒫₂; otherwise it is irreducible. We prove that the factorization of a reducible hereditary property into irreducible factors is unique whenever the property is additive, i.e., it is closed under the disjoint union of graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 44–53, 2000     

Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and [h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t] and orthodox-[h,2,t] graphs for varied values of h and t.     

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

10阶无弓形链环图

证明边数等于10的3‖δ_(v,f)-平图在连通性和顶点最大度条件限制下的三个唯一性结论,进而确定10阶无弓形链环图.     

Tight products and graph expansion

In this article, we study a new product of graphs called tight product. A graph H is said to be a tight product of two (undirected multi) graphs G₁ and G₂, if V(H) = V(G₁) × V(G₂) and both projection maps V(H)→V(G₁) and V(H)→V(G₂) are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is NP‐hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class‐1 (2k+ 1)‐regular graphs. We also obtain a new model of random d‐regular graphs whose second eigenvalue is almost surely at most O(d^3/4). This construction resembles random graph lifts, but requires fewer random bits. © 2011 Wiley Periodicals, Inc. J Graph Theory     

T-型树谱唯一性的一个简单刻画

图G称为谱唯一的,如果任何与G谱相同的图一定与G同构.一棵树称为T-型树如果其仅有一个最大度为3的顶点.本文给出了T-型树谱唯一性的一个简单刻画,从而完全解决了T-型树的谱唯一性问题.     

Representing edge intersection graphs of paths on degree 4 trees

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G=EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.