A class of symmetric graphs with 2‐arc transitive quotients

Let Γ be an X‐symmetric graph admitting an X‐invariant partition ?? on V(Γ) such that Γ_?? is connected and (X, 2)‐arc transitive. A characterization of (Γ, X, ??) was given in [S. Zhou Eur J Comb 23 (2002), 741–760] for the case where |B|>|Γ(C)∩B|=2 for an arc (B, C) of Γ_??.We con‐sider in this article the case where |B|>|Γ(C)∩B|=3, and prove that Γ can be constructed from a 2‐arc transitive graph of valency 4 or 7 unless its connected components are isomorphic to 3 K ₂, C ₆ or K _{3, 3}. As a byproduct, we prove that each connected tetravalent (X, 2)‐transitive graph is either the complete graph K ₅ or a near n‐gonal graph for some n?4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 232–245, 2010     

On perfect Γ‐decompositions of the complete graph

Generalizing the well‐known concept of an i‐perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a Γ‐decomposition (Γ‐factorization) of a complete graph K_v to be i‐perfect if for every edge [x, y] of K_v there is exactly one block of the decomposition (factor of the factorization) in which x and y have distance i. In particular, a Γ‐decomposition (Γ‐factorization) of K_v that is i‐perfect for any i not exceeding the diameter of a connected graph Γ will be said a Steiner (Kirkman) Γ‐system of order v. In this article we first observe that as a consequence of the deep theory on decompositions of edge‐colored graphs developed by Lamken and Wilson [Lamken and Wilson, 2000, J Combin Theory Ser A 89, 149–200], there are infinitely many values of v for which there exists an i‐perfect Γ‐decomposition of K_v provided that Γ is an i‐equidistance graph, namely a graph such that the number of pairs of vertices at distance i is equal to the number of its edges. Then we give some concrete direct constructions for elementary abelian Steiner Γ‐systems with Γ the wheel on 8 vertices or a circulant graph, and for elementary abelian 2‐perfect cube‐factorizations. We also present some recursive constructions and some results on 2‐transitive Kirkman Γ‐systems. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 197–209, 2009     

An asymptotic version of a conjecture by Enomoto and Ota

In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let G be a graph of order n, and let n₁, n₂, …, n_k be positive integers with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} {{n}}_{{{i}}} = {{n}}\end{eqnarray*}. If σ₂(G)≥n+ k?1, then for any k distinct vertices x₁, x₂, …, x_k in G, there exist vertex disjoint paths P₁, P₂, …, P_k such that |P_i|=n_i and x_i is an endpoint of P_i for every i, 1≤i≤k. We prove an asymptotic version of this conjecture in the following sense. For every k positive real numbers γ₁, …, γ_k with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} \gamma_{{{i}}} = {{1}}\end{eqnarray*}, and for every ε>0, there exists n₀ such that for every graph G of order n≥n₀ with σ₂(G)≥n+ k?1, and for every choice of k vertices x₁, …, x_k∈V(G), there exist vertex disjoint paths P₁, …, P_k in G such that \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} |{{P}}_{{{i}}}| = {{n}}\end{eqnarray*}, the vertex x_i is an endpoint of the path P_i, and (γ_i?ε)n<|P_i|<(γ_i + ε)n for every i, 1≤i≤k. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010     

Localization and Catenarity in Iterated Differential Operator Rings

ABSTRACT

Let k be a field, R an associative k-algebra with identity, Δ a finite set of derivations of R, and R[Θ₁, δ₁] ··· [Θ _n , δ _n ] an iterated differential operator k-algebra over R such that δ _j (Θ _i ) ∈ R[Θ₁, δ₁] ··· [Θ _i?1, δ _i?1]; 1 ≤ i < j ≤ n. If R is Noetherian Δ-hypercentral, then every prime ideal P of A is classically localizable. The aim of this article is to show that under some additional hypotheses on the Δ-prime ideals of R, the local ring A _P is regular in the sense of Robert Walker. We use this result to study the catenarity of A and to compute the numbers μ _i of Bass. Let g be a nilpotent Lie algebra of finite dimension n acting on R by derivations and U(g) the enveloping algebra of g. Then the crossed product of R by U(g) is an iterated differential operator k-algebra as above. In this particular case, our results are known if k has characteristic zero.     

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009     

The Leading Ideal of a Complete Intersection of Height Two in a 2-Dimensional Regular Local Ring

Let (S,𝔫) be a 2-dimensional regular local ring and let I = (f, g) be an ideal in S generated by a regular sequence f, g of length two. Let I* be the leading ideal of I in the associated graded ring gr𝔫(S), and set R = S/I and 𝔪 = 𝔫/I. In Goto et al. (2007 Goto , S. , Heinzer , W. , Kim , M.-K. ( 2007 ). The leading ideal of a complete intersection of height two, II . J. Algebra 312 : 709 – 732 . [Google Scholar]), we prove that if μ _G (I*) = n, then I* contains a homogeneous system {ξ _i }_1≤i≤n of generators such that deg ξ _i  + 2 ≤ deg ξ _i+1 for 2 ≤ i ≤ n ? 1, and ht _G (ξ₁, ξ₂,…, ξ _n?1) = 1, and we describe precisely the Hilbert series H(gr𝔪(R), λ) in terms of the degrees c _i of the ξ _i and the integers d _i , where d _i is the degree of D _i  = GCD(ξ₁,…, ξ _i ). To the complete intersection ideal I = (f, g)S we associate a positive integer n with 2 ≤ n ≤ c ₁ + 1, an ascending sequence of positive integers (c ₁, c ₂,…, c _n ), and a descending sequence of integers (d ₁ = c ₁, d ₂,…, d _n  = 0) such that c _i+1 ? c _i  > d _i?1 ? d _i  > 0 for each i with 2 ≤ i ≤ n ? 1. We establish here that this necessary condition is also sufficient for there to exist a complete intersection ideal I = (f, g) whose leading ideal has these invariants. We give several examples to illustrate our theorems.     

A class of Hamiltonian and edge symmetric Cayley graphs on symmetric groups

Abstract. Let Sn be the symmetric group     

Catenarian Property of Mixed Polynomial and Power Series Rings Over a Pullback

Let T be an integral domain with a maximal ideal M, ?: T → K: = T/M the natural surjection, and R the pullback ?^?1(D), where D is a proper subring of K. We give necessary and sufficient conditions for the mixed extensions R[x ₁]]…[x _n ]] to be catenarian, where each [x _i ]] is fixed as either [x _i ] or [[x _i ]]. We also give a complete answer to the question of determining the field extensions k ? K such that the contraction map Spec(K[x ₁]]…[x _n ]]) → Spec(k[x ₁]]…[x _n ]]) is a homeomorphism. As an application, we characterize the globalized pseudo-valuation domains R such that R[x ₁]]…[x _n ]] is catenarian.     

A New Construction for Cohen–Macaulay Graphs

Let G be a finite simple graph on a vertex set V(G) = {x ₁₁,…, x _n1}. Also let m ₁,…, m _n  ≥ 2 be integers and G ₁,…, G _n be connected simple graphs on the vertex sets V(G _i ) = {x _i1,…, x _{im i} }. In this article, we provide necessary and sufficient conditions on G ₁,…, G _n for which the graph obtained by attaching the G _i to G is unmixed or vertex decomposable. Then we characterize Cohen–Macaulay and sequentially Cohen–Macaulay graphs obtained by attaching the cycle graphs or connected chordal graphs to arbitrary graphs.     

Chains of Rings with Local Formal Fibers

Let (T, M) be a complete local domain containing the integers. Let p ₁ ? p ₂ ? ··· ? p _n be a chain of nonmaximal prime ideals of T such that T _{p n} is a regular local ring. We construct a chain of excellent local domains A _n  ? A _n?1 ? ··· ? A ₁ such that for each 1 ≤ i ≤ n, the completion of A _i is T, the generic formal fiber of A _i is local with maximal ideal p _i , and if I is a nonzero ideal of A _i then A _i /I is complete. We then show that if Q is a nonmaximal prime ideal of T and 1 ≤ h = ht _T Q, then there is a chain of excellent local domains B ₀ ? B ₁ ? ··· ? B _h  ? T such that for every i = 0, 1, 2,…, h we have ht(Q ∩ B _i ) = i, the completion of B _i is isomorphic to T[[X ₁, X ₂,…, X _i ]] where the X _j 's are indeterminants, and the formal fiber of Q ∩ B _i is local.     

Minimal graded free resolutions for monomial curves in 𝔸4 defined by almost arithmetic sequences

Let m = (m₀, m₁, m₂, n) be an almost arithmetic sequence, i.e., a sequence of positive integers with gcd(m₀, m₁, m₂, n) = 1, such that m₀ < m₁ < m₂ form an arithmetic progression, n is arbitrary and they minimally generate the numerical semigroup Γ =m₀? +m₁? +m₂? +n?. Let k be a field. The homogeneous coordinate ring k[Γ] of the affine monomial curve parametrically defined by X₀ = t^m₀, X₁ = t^m₁, X₂ = t^m₂, Y = tⁿ is a graded R-module, where R is the polynomial ring k[X₀, X₁, X₂, Y] with the grading degX_i: = m_i, degY: = n. In this paper, we construct a minimal graded free resolution for k[Γ].     

On a Question of Glasby,Praeger, and Xia

A Jordan partition λ(m, n, p) = (λ₁, λ₂, … , λ _m ) is a partition of mn associated with the expression of a tensor V _m  ? V _n of indecomposable KG-modules into a sum of indecomposables, where K is a field of characteristic p and G a cyclic group of p-power order. It is standard if λ _i  = m + n ? 2i + 1 for all i. We answer a recent question of Glasby, Praeger, and Xia who asked for necessary and sufficient conditions for λ(m, n, p) to be standard.     

Depth of Initial Ideals of Normal Edge Rings

Let G be a finite graph on the vertex set [d] = {1,…, d} with the edges e ₁,…, e _n and K[t] = K[t ₁,…, t _d ] the polynomial ring in d variables over a field K. The edge ring of G is the semigroup ring K[G] which is generated by those monomials t ^e  = t _i t _j such that e = {i, j} is an edge of G. Let K[x] = K[x ₁,…, x _n ] be the polynomial ring in n variables over K, and define the surjective homomorphism π: K[x] → K[G] by setting π(x _i ) = t ^{e _i} for i = 1,…, n. The toric ideal I _G of G is the kernel of π. It will be proved that, given integers f and d with 6 ≤ f ≤ d, there exists a finite connected nonbipartite graph G on [d] together with a reverse lexicographic order <_rev on K[x] and a lexicographic order <_lex on K[x] such that (i) K[G] is normal with Krull-dim K[G] = d, (ii) depth K[x]/in_<rev (I _G ) = f and K[x]/in_<lex (I _G ) is Cohen–Macaulay, where in_<rev (I _G ) (resp., in_<lex (I _G )) is the initial ideal of I _G with respect to <_rev (resp., <_lex) and where depth K[x]/in_<rev (I _G ) is the depth of K[x]/in_<rev (I _G ).     

Numerical Semigroup Rings and Almost Prüfer v-Multiplication Domains

Let D be an integral domain with quotient field K, X be an indeterminate over D, Γ be a numerical semigroup with Γ ? ?₀, D[Γ] be the semigroup ring of Γ over D (and hence D ? D[Γ] ? D[X]), and D + X ⁿ K[X] = {a + X ⁿ g∣a ∈ D and g ∈ K[X]}. We show that there exists an order-preserving bijection between Spec(D[X]) and Spec(D[Γ]), which also preserves t-ideals. We also prove that D[Γ] is an APvMD (resp., AGCD-domain) if and only if D[X] is an APvMD (resp., AGCD-domain) and char(D) ≠ 0. We show that if n ≥ 2, then D is an APvMD (resp., AGCD-domain, AGGCD-domain, AP-domain, AB-domain) and char(D) ≠ 0 if and only if D + X ⁿ K[X] is an APvMD (resp., AGCD-domain, AGGCD-domain, AP-domain, AB-domain). Finally, we give some examples of APvMDs which are not AGCD-domains by using the constructions D[Γ] and D + X ⁿ K[X].     

Spectra of Extended Double Cover Graphs

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v ₁, v ₂, ..., v _n }, the extended double cover of G, denoted G ^*, is the bipartite graph with bipartition (X, Y) where X = {x ₁, x ₂, ..., x _n } and Y = {y ₁, y ₂, ..., y _n }, in which x _i and y _j are adjacent iff i = j or v _i and v _j are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G ^* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G ^* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented.     

S-Noetherian Rings of the Forms 𝒜[X] and 𝒜[[X]]

Let 𝒜 = (A _n ) _n≥0 be an ascending chain of commutative rings with identity, S ? A ₀ a multiplicative set of A ₀, and let 𝒜[X] (respectively, 𝒜[[X]]) be the ring of polynomials (respectively, power series) with coefficient of degree i in A _i for each i ∈ ?. In this paper, we give necessary and sufficient conditions for the rings 𝒜[X] and 𝒜[[X]] to be S ? Noetherian.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

Degree series of the 3-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant λ such that the equality λd（vi） = Σ（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,..., ｜V（G）｜, where d（vi） denotes the degree of vertex vi. Let ni denote the number of vertices with degree i. This paper deals with the 3-Hgraphs and determines their degree series. Moreover, the 3-Hgraphs with bounded ni （1 ≤ i ≤ 7） are studied and some interesting results are obtained.     

Regular Steinhaus graphs of odd degree

A Steinhaus matrix is a binary square matrix of size n which is symmetric, with a diagonal of zeros, and whose upper-triangular coefficients satisfy a_i,j=a_i−1,j−1+a_i−1,j for all 2?i<j?n. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices K₂ is the only regular Steinhaus graph of odd degree. Using Dymacek’s theorem, we prove that if (a_i,j)_1?i,j?n is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix (a_i,j)_2?i,j?n−1 is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size n whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on parameters for all even numbers n, and on parameters in the odd case. This result permits us to verify Dymacek’s conjecture up to 1500 vertices in the odd case.     

Group action for enumerating maps on surfaces

A map is a connected topological graph Γ cellularly embedded in a surface. For any connected graph Γ, by introducing the conception of semi-arc automorphism groupAut1/2 Γ and classifying all embedding of Γ under the action of this group, the numbersr ^o (Γ) andr ^N (Γ) of rooted maps on orientable and non-orientable surfaces with underlying graph Γ are found. Many closed formulas without sum Σ for the number of rooted maps on surfaces (orientable or non-orientable) with given underlying graphs, such as, complete graphK _n , complete bipartite graphK _m,n, bouquetsB _n , dipoleDp _n and generalized dipoleDp _n ^k,l are refound in this paper.