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.     

Chromatically Supremal Decompositions of Graphs

If G is a graph, a G-decomposition of a host graph H is a partition of the edges of H into subgraphs of H which are isomorphic to G. The chromatic index of a G-decomposition of H is the minimum number of colors required to color the parts of the decomposition so that parts which share a common node get different colors. We establish an upper bound on the chromatic index and characterize those decompositions which achieve it. The structurally most interesting of the decompositions with maximal chromatic index are associated with (v, k, 1)-designs.     

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.     

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 Complete Multipartite Graphs into Cycles of Even Length

Necessary and sufficient conditions for the existence of an edge-disjoint decomposition of any complete multipartite graph into even length cycles are investigated. Necessary conditions are listed and sufficiency is shown for the cases when the cycle length is 4, 6 or 8. Further results concerning sufficiency, provided certain “small” decompositions exist, are also given for arbitrary even cycle lengths. Revised: November 28, 1997     

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.     

6个素数阶完全图的循环图分解

研究素数阶完全图分解为循环图的方法 ,给出计算它的子图的团数的一种算法 ,得到 3个三色 ,3个四色 Ramsey数的新的下界 :R(3,3,13) 194 ,R(3,4 ,11) 2 12 ,R(3,6 ,13) 52 2 ,R(3,3,4 ,10 ) 380 ,R(3,3,6 ,14) 1154,R(3,4 ,5,13) 10 94     

Large Sets of Hamilton Cycle and Path Decompositions of Complete Bipartite Graphs

In this paper, we determine the existence spectrums for large sets of Hamilton cycle and path (resp. directed Hamilton cycle and path) decompositions of ??K _{m, n} (resp. ${\lambda K^{*}_{m,n}}$ ).     

半线性微分方程的概自守与伪概自守解

在Banach空间中,利用发展系统的算子半群理论和Banach压缩原理,在半线性微分方程x′（t）=A（t）x（t）＋f（t,x（t））满足一定的条件下,证明了其概自守与伪概自守mild解的存在性与唯一性．     

Automorphic Objects in Categories

Siberian Mathematical Journal -     

Automorphic Plancherel density theorem

Let F be a totally real field, G a connected reductive group over F, and S a finite set of finite places of F. Assume that G(F ?_? ?) has a discrete series representation. Building upon work of Sauvageot, Serre, Conrey-Duke-Farmer and others, we prove that the S-components of cuspidal automorphic representations of $G\left( {\mathbb{A}_F } \right)$ are equidistributed with respect to the Plancherel measure on the unitary dual of G(F _S ) in an appropriate sense. A few applications are given, such as the limit multiplicity formula for local representations in the global cuspidal spectrum and a quite flexible existence theorem for cuspidal automorphic representations with prescribed local properties. When F is not a totally real field or G(F ?_? ?) has no discrete series, we present a weaker version of the above results.     

Extreme Values of Automorphic L-Functions

Ω-theorems for some automorphic L-functions and, in particular, for the Rankin?Selberg L-function L(s, f × f) are considered. For example, as t tends to infinity, $$ \log \left| {L\left( {\frac{1}{2}+it,f\times f} \right)} \right|={\varOmega_{+}}\left( {{{{\left( {\frac{{\log t}}{{\log\;\log t}}} \right)}}^{1/2 }}} \right) $$ and $$ \log \left| {L\left( {{\sigma_0}+it,f\times f} \right)} \right|={\varOmega_{+}}\left( {{{{\left( {\frac{{\log t}}{{\log\;\log t}}} \right)}}^{{1-{\sigma_0}}}}} \right) $$ For a fixed σ ₀ ∈ $ \left( {\frac{1}{2},1} \right) $ . Bibliography: 15 titles.     

Automorphic Equivalence of Many-Sorted Algebras

For every variety Θ of universal algebras we can consider the category Θ⁰ of the finite generated free algebras of this variety. The quotient group \(\mathfrak {A/Y}\), where \(\mathfrak {A}\) is a group of all the automorphisms of the category Θ⁰ and \(\mathfrak {Y}\) is a subgroup of all the inner automorphisms of this category measures difference between the geometric equivalence and automorphic equivalence of algebras from the variety Θ. In Plotkin and Zhitomirski (J. Algebra 306(2), 344–367, 2006) the simple and strong method of the verbal operations was elaborated on for the calculation of the group \(\mathfrak {A/Y} \) in the case when the Θ is a variety of one-sorted algebras. In the first part of our paper (Sections 1, 2 and 3) we prove that this method can be used in the case of many-sorted algebras. In the second part of our paper (Section 4) we apply the results of the first part to the universal algebraic geometry of many-sorted algebras and prove again and refine the results of Plotkin (2003) and Tsurkov (Int. J. Algebra Comput. 17(5/6), 1263–1271, 2007) for these algebras. For example we prove in the Theorem 4.3 that the automorphic equivalence of algebras can be reduced to the geometric equivalence if we change the operations in one of these algebras. In the third part of this paper (Section 5) we consider some varieties of many-sorted algebras. We prove that automorphic equivalence coincides with geometric equivalence in the variety of all the actions of semigroups over sets and in the variety of all the automatons, because the group \(\mathfrak {A/Y}\) is trivial for these varieties. We also consider the variety of all the representations of groups and all the representations of Lie algebras. The group \(\mathfrak {A/Y}\) is not trivial for these varieties and for both these varieties we give an examples of the representations which are automorphically equivalent but not geometrically equivalent.     

Constructions of Commutative Automorphic Loops

A loop whose inner mappings are automorphisms is an automorphic loop (or A-loop). We characterize commutative (A-)loops with middle nucleus of index 2 and solve the isomorphism problem. Using this characterization and certain central extensions based on trilinear forms, we construct several classes of commutative A-loops of order a power of 2. We initiate the classification of commutative A-loops of small orders and also of order p ³, where p is a prime.     

Decompositions of rings

Translated from Matematicheskie Zametki, Vol. 57, No. 1, pp. 137–139, January, 1995.     

Higher-Dimensional Automorphic Lie Algebras

The paper presents the complete classification of Automorphic Lie Algebras based on \({{\mathfrak {sl}}}_{n}(\mathbb {C})\), where the symmetry group G is finite and acts on \({{\mathfrak {sl}}}_n(\mathbb {C})\) by inner automorphisms, \({{\mathfrak {sl}}}_n(\mathbb {C})\) has no trivial summands, and where the poles are in any of the exceptional G-orbits in \(\overline{\mathbb {C}}\). A key feature of the classification is the study of the algebras in the context of classical invariant theory. This provides on the one hand a powerful tool from the computational point of view; on the other, it opens new questions from an algebraic perspective (e.g. structure theory), which suggest further applications of these algebras, beyond the context of integrable systems. In particular, the research shows that this class of Automorphic Lie Algebras associated with the \(\mathbb {T}\mathbb {O}\mathbb {Y}\) groups (tetrahedral, octahedral and icosahedral groups) depend on the group through the automorphic functions only; thus, they are group independent as Lie algebras. This can be established by defining a Chevalley normal form for these algebras, generalising this classical notion to the case of Lie algebras over a polynomial ring.