Pairs of Chromatically Equivalent Graphs

Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. In this paper we give the means to construct infinitely many pairs of chromatically equivalent graphs where one graph in the pair is clique-separable, that is, can be obtained by identifying an r-clique in some graph H ₁ with an r-clique in some graph H ₂, and the other graph is non-clique-separable. There are known methods for finding pairs of chromatically equivalent graphs where both graphs are clique-separable or both graphs are non-clique-separable. Although examples of pairs of chromatically equivalent graphs where only one of the graphs is clique-separable are known, a method for the construction of infinitely many such pairs was not known. Our method constructs such pairs of graphs with odd order n ≥ 9.     

Decompositions of Complete Graphs

If s₁, s₂, ..., s_t are integers such that n – 1 = s₁ +s₂ + ... + s_t and such that for each i (1 i t), 2 s_i n –1 and s_in is even, then K_n can be expressed as the union G₁G₂...G_tof t edge-disjoint factors, where for each i, G_i is s_i-regularand s_i-connected. Moreover, whenever s_i = s_j, G_i and G_j areisomorphic. 1991 Mathematics Subject Classification 05C70.     

Induced Decompositions of Graphs

We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.     

On Cyclic Decompositions of Complete Graphs into Tripartite Graphs

We introduce two new labelings for tripartite graphs and show that if a graph G with n edges admits either of these labelings, then there exists a cyclic G‐decomposition of for every positive integer x. We also show that if G is the union of two vertext‐disjoint cycles of odd length, other than , then G admits one of these labelings.     

Induced Decompositions of Highly Dense Graphs

Given two graphs F and G, an induced F‐decomposition of G is a partition of into induced subgraphs isomorphic to F. Bondy and Szwarcfiter [J. Graph Theory, DOI: 10.1002/jgt.21654] defined the value as the maximum number of edges in a graph of order n admitting an induced F‐decomposition and determined the value of for some graphs (and families of graphs). In this article, we prove that is valid for all graphs F. We also present tighter asymptotic bounds for some of the small graphs for which the exact value of remains unknown. The proofs are based on the heavy use of various classes of Kneser graphs and hypergraphs.     

Ear Decompositions of Matching Covered Graphs

G different from and has at least Δ edge-disjoint removable ears, where Δ is the maximum degree of G. This shows that any matching covered graph G has at least Δ! different ear decompositions, and thus is a generalization of the fundamental theorem of Lovász and Plummer establishing the existence of ear decompositions. We also show that every brick G different from and has Δ− 2 edges, each of which is a removable edge in G, that is, an edge whose deletion from G results in a matching covered graph. This generalizes a well-known theorem of Lovász. We also give a simple proof of another theorem due to Lovász which says that every nonbipartite matching covered graph has a canonical ear decomposition, that is, one in which either the third graph in the sequence is an odd-subdivision of or the fourth graph in the sequence is an odd-subdivision of . Our method in fact shows that every nonbipartite matching covered graph has a canonical ear decomposition which is optimal, that is one which has as few double ears as possible. Most of these results appear in the Ph. D. thesis of the first author [1], written under the supervision of the second author. Received: November 3, 1997     

On Connected Resolving Decompositions in Graphs

For an ordered k-decomposition of a connected graph G and an edge e of G, the -code of e is the k-tuple where d(e, G _i) is the distance from e to G _i. A decomposition is resolving if every two distinct edges of G have distinct -codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dim _d (G). A resolving decomposition of G is connected if each G _i is connected for 1 i k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 dim _d (G) cd(G) m for every connected graph G of size m 2. All nontrivial connected graphs of size m with connected decomposition number 2 or m have been characterized. We present characterizations for connected graphs of size m with connected decomposition number m – 1 or m – 2. It is shown that each pair s, t of rational numbers with 0 < s t 1, there is a connected graph G of size m such that dim _d (G)/m = s and cd(G)/m = t.     

Monochromatic Kr‐Decompositions of Graphs

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a monochromatic graph isomorphic to H. Let be the smallest number ? such that any graph G of order n and any coloring of its edges with k colors, admits a monochromatic H‐decomposition with at most ? parts. Here, we study the function for and .     

Petersen Graph Decompositions of Complete Multipartite Graphs

Let P be the Petersen graph, and K _u(h) the complete multipartite graph with u parts of size h. A decomposition of K _u(h) into edge-disjoint copies of the Petersen graph P is called a P-decomposition of K _u(h) or a P-group divisible design of type h ^u . In this paper, we show that there exists a P-decomposition of K _u(h) if and only if h²u(u-1) o 0 mod 30{h^2u(u-1)\equiv 0 \pmod {30}} , h(u-1) o 0 mod 3{h(u-1)\equiv 0\pmod 3} , and u ≥ 3 with a definite exception (h, u) = (1, 10).     

构造色等价图的几种新方法

给出了构造伴随等价图的几种新方法，因而也给出了构造色等价图的几种新方法。     

Rank 3 Transitive Decompositions of Complete Multipartite Graphs

A transitive decomposition of a graph is a partition of the edge or arc set giving a set of subgraphs which are preserved and permuted transitively by a group of automorphisms of the graph. This paper deals with transitive decompositions of complete multipartite graphs preserved by an imprimitive rank 3 permutation group. We obtain a near-complete classification of these when the group in question has an almost simple component.     

Decompositions of Graphs into Fans and Single Edges

Given two graphs G and H , an H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H . Let be the smallest number ? such that any graph G of order n admits an H‐decomposition with at most ? parts. Pikhurko and Sousa conjectured that for and all sufficiently large n , where denotes the maximum number of edges in a graph on n vertices not containing H as a subgraph. Their conjecture has been verified by Özkahya and Person for all edge‐critical graphs H . In this article, the conjecture is verified for the k‐fan graph. The k‐fan graph , denoted by , is the graph on vertices consisting of k triangles that intersect in exactly one common vertex called the center of the k‐fan.     

伴随多项式的根与色等价图的刻画

文[2]给出了不含三角形图伴随多项式根的内插性质,本文研究了含三角形图的伴随多项式根的性质,在此基础上完整地刻画了■的色等价图,且给出这类图色唯一的充要条件.Cti表示有ti个顶点的圈;Dn表示Pn-2的一个1度点粘接下来K3的一个点得到的图.     

SG类图簇的伴随多项式的因式分解及色性分析

设G是任意的P阶连通图，V(G)={V1，V2，…，Vp}，Sn 1是具有度序列(n，1，1，…，1)的．n 1阶星图．令(ψ)^G(i）(n，P)表示图G的第i个顶点与Sn 1的n度点重迭后得到的图；Srp 1^G（i）表示rG的每个分支的第i个顶点依次与Sr 1的r个1度点重迭后得到的图，这里n≥1，P≥2，1≤i≤P．我们通过研究图的伴随多项式的因式分解，证明了两个图簇Srp 1^G(i）U（r-1)K1与(r-1)GUψG(i)(r,P)的补图是色等价的，但它们均不是色唯一的，从而推广了张秉儒证明的文[14]中的定理1。     

有限循环群上的Cayley有向图的哈密顿分解

本文给出了有限循环群上的Cayley有向图Cay(M,G)可哈密顿分解的一个充分条件,并证明了当|M|=2时此条件还是必要的.     

Ascending Subgraph Decompositions in Oriented Complete Balanced Tripartite Graphs

In 1987, Alavi, Boals, Chartrand, Erdös, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). Though different classes of graphs have been shown to have an ASD, the conjecture remains open. In this paper we investigate the similar problem for digraphs. In particular, we will show that any orientation of a compete balanced tripartite graph has an ASD.     

几类图簇的伴随多项式的因式分解及色性分析

我们通过研究图的伴随多项式的因式分解，给出了证明非色唯一图的一种新方法，并得到了几类图簇的色等价图的结构特征．     

On Rooted Packings,Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted ‐packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ‐packings in this case.