On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

Covering a Connected Curve on the Torus with Squares

We throw i.i.d. random squares S ₁,S ₂,… with respective side lengths l ₁,l ₂,… uniformly on the two-dimensional torus ?/?×?/?, where $\{l_{n}\}_{n=1}^{\infty}$ is a nonincreasing sequence with 0<l _n <1 and lim _n→∞ l _n =0. A necessary and sufficient condition for covering the connected curve {0}×?/? is $$\sum_{n=1}^{\infty}\frac{l_n}{(\sum_{i=1}^{n}l_i)^2}\exp{\Biggl(\sum _{i=1}^{n}l_i^2\Biggr)}=\infty.$$      

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.     

Accretion centers: A generalization of branch weight centroids

An ordered n-tuple (v_i1,v_i2,…,v_in) is called a sequential labelling of graph G if {v_i1,v_i2,…,v_in} = V(G) and the subgraph induced by {v_i1,v_i2,…, v_ij} is connected for 1≤j≤n. Let σ(v;G) denote the number of sequential labellings of G with v_i1=v. Vertex v is defined to be an accretion center of G if σ is maximized at v. This is shown to generalize the concept of a branch weight centroid of a tree since a vertex in a tree is an accretion center if and only if it is a centroid vertex. It is not, however, a generalization of the concept of a median since for a general graph an accretion center is not necessarily a vertex of minimum distance. A method for computing σ(v;G) based upon edge contractions is described.     

Elasticity of factorizations in R 0 + X R1 + … + X lRl [X]

For an atomic domain R the elasticity ρ(R) is defined by ρ(R) = sup{m/n ¦ u₁ … u _m = v ₁ … v_n where u_i, v_i ∈ R are irreducible}. Let R ₀ ? … ? R _l be an ascending chain of domains which are finitely generated over ? and assume that R _l is integral over R ₀. Let X be an indeterminate. In this paper we characterize all domains D of the form D = R ₀ + XR₁ + … + X^lR_l[X] whose elasticity ρ(D) is finite.     

On the respective terms of the derived and the polycentral series of a free lie algabra and an ideal

Let F be a free Lie algebra of rank> 1 and S be an ideal of F. Denote by F_m and F_{n l},…,n_k the terms of the lower central and the polycentral series of F. The aim of this paper is to provide a sufficient condition for the quotient algebra F_{n l},…,n_k/S_{n l},…,n_k to be infinitely generated. The case F_m/S_m was studied in [6] for free groups and in [ 2 ] for free Lie algebras. In this paper the following main theorem is proved : If F = F2 = S, k > 1 and n_i > 1 for i=l,…, k, then F_{n l}…,n_k/S_{n l} is infinitely generated.     

Distribution of an analog of Sherman's statistics under rank-censored observations

Let U_n(1),..., U_n(n) be a variational series constructed from a sequence of n aggregate-independent random variables distributed uniformly on (0, 1). Let 0 = k₀, k₁,..., k_m, k_m+1= n+1 be an increasing sequence of nonnegative integers, λ= k_r+1?k_r, r=0,..., m, and $$\xi _n = \frac{1}{2}\sum\nolimits_{r = 0}^m {\left| {U_n (k_{r + 1} ) - U_n^\prime (k_r ) - \frac{{k_{r + 1} - k_r }}{{n + 1}}} \right|.}$$ Under certain restrictions on the numbers λ_r= k{r+1}?k_r, in this paper we have shown the asymptotic normality (with an appropriate norming) of the quantity ξ_n as n, m →∞ such that lim sup (m/√n) ar ∞.     

Orientations of circle graphs

Let C(v₁, …,v_n) be a system consisting of a circle C with chords v₁, …,v_n on it having different endpoints. Define a graph G having vertex set V(G) = {v₁, …,v_n} and for which vertices v_i and v_j are adjacent in G if the chords v_i and v_j intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v₁, …,v_n) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v₁, …,v_n) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.     

Maximal antiramsey graphs and the strong chromatic number

A typical problem arising in Ramsey graph theory is the following. For given graphs G and L, how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper we investigate the opposite extreme. That is, we will require that in any subgraph of G isomorphic to L, all its edges have different colors. We call such a subgraph a totally multicolored copy of L. Of particular interest to us will be the determination of X_s(n, e, L), defined to be the minimum number of colors needed to edge-color some graph G(n, ?) with n vertices and e edges so that all copies of L in it are totally multicolored. It turns out that some of these questions are surprisingly deep, and are intimately related, for example, to the well-studied (but little understood) functions r_k(n), defined to be the size of the largest subset of {1, 2,…, n} containing no k-term arithmetic progression, and g(n; k, l), defined to be the maximum number of triples which can be formed from {1, 2,…, n} so that no two triples share a common pair, and no k elements of {1, 2,…, n} span l triples.     

On the spectral radius of ‡-shape trees

Let A(G) be the adjacency matrix of G. The characteristic polynomial of the adjacency matrix A is called the characteristic polynomial of the graph G and is denoted by φ(G, λ) or simply φ(G). The spectrum of G consists of the roots (together with their multiplicities) λ ₁(G) ? λ ₂(G) ? … ? λ _n (G) of the equation φ(G, λ) = 0. The largest root λ ₁(G) is referred to as the spectral radius of G. A ?-shape is a tree with exactly two of its vertices having maximal degree 4. We will denote by G(l ₁, l ₂, … l ₇) (l ₁ ? 0, l _i ? 1, i = 2, 3, …, 7) a ?-shape tree such that $G\left( {l_1 ,l_2 , \ldots l_7 } \right) - u - v = P_{l_1 } \cup P_{l_2 } \cup \ldots P_{l_7 }$ , where u and v are the vertices of degree 4. In this paper we prove that ${{3\sqrt 2 } \mathord{\left/ {\vphantom {{3\sqrt 2 } 2}} \right. \kern-0em} 2} < \lambda _1 \left( {G\left( {l_1 ,l_2 , \ldots l_7 } \right)} \right) < {5 \mathord{\left/ {\vphantom {5 2}} \right. \kern-0em} 2}$ .     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

Commuting Values of Generalized Derivations on Multilinear Polynomials

Let K be a commutative ring with unity, R a prime K-algebra of characteristic different from 2, U the right Utumi quotient ring of R, f(x ₁,…, x _n ) a noncentral multilinear polynomial over K, and G a nonzero generalized derivation of R. Denote f(R) the set of all evaluations of the polynomial f(x ₁,…, x _n ) in R. If [G(u)u, G(v)v] = 0, for any u, v ∈ f(R), we prove that there exists c ∈ U such that G(x) = cx, for all x ∈ R and one of the following holds: 1. f(x ₁,…, x _n )² is central valued on R;

2. R satisfies s ₄, the standard identity of degree 4.

     

k-ordered Hamiltonian graphs

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices, G contains a v₁-v_k hamiltonian path that encounters v₁, v₂,…, v_k in this order. It is shown that for k ≥ 3, every (k + 1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs. © 1997 John Wiley & Sons, Inc.     

On Ramsey numbers involving starlike multipartite graphs

The Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,₁, n₂, …. n_k). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m₁, …. m_k), K(1, n)), r(K(1, m), K(n₁, …. n_k, n)), provided m ≧ 4, and r(K(1, 1, m), K(n_k, …, n_k, n)).     

Alternating eulerian trails with prescribed degrees in two edge-colored complete graphs

Let K_n be the complete graph with vertex set {v₁, v₂, …, v_n} and let g=(g₁, …, g_n) be a sequence of positive integers. Color each edge of this K_n red or blue. In this paper necessary and sufficient conditions are given which guarantee the existence of a connected spanning subgraph F in K_n (as colored) with both red degree and blue degree in F at vertex v₁ equal to g_i. When each g_i = 1 this answers a question of Erdös proved in this special case in [1].     

Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      17. Optimal labelling of a product of two paths      Jarmila Chvátalová 《Discrete Mathematics》1975,11(3):249-253 If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.Pn will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. Pm × Pn will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(Pm × Pn) = min(m, n).      18. A New Construction for Cohen–Macaulay Graphs      Amir Mousivand  Seyed Amin Seyed Fakhari  Siamak Yassemi 《代数通讯》2013,41(12):5104-5112 Let G be a finite simple graph on a vertex set V(G) = {x 11,…, x n1}. Also let m 1,…, m n  ≥ 2 be integers and G 1,…, 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 1,…, 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.      19. On the groups of unitriangular automorphisms of relatively free groups      S. Yu. Erofeev  V. A. Roman’kov 《Siberian Mathematical Journal》2012,53(5):792-799 We describe the structure of the group U n of unitriangular automorphisms of the relatively free group G n of finite rank n in an arbitrary variety C of groups. This enables us to introduce an effective concept of normal form for the elements and present U n by using generators and defining relations. The cases n = 1, 2 are obvious: U 1 is trivial, and U 2 is cyclic. For n ?? 3 we prove the following: If G n?1 is a nilpotent group then so is U n . If G n?1 is a nilpotent-by-finite group then U n admits a faithful matrix representation. But if the variety C is different from the variety of all groups and G n?1 is not nilpotent-by-finite then U n admits no faithful matrix representation over any field. Thus, we exhaustively classify linearity for the groups of unitriangular automorphisms of finite rank relatively free groups in proper varieties of groups, which complements the results of Olshanskii on the linearity of the full automorphism groups AutG n . Moreover, we introduce the concept of length of an automorphism of an arbitrary relatively free group G n and estimate the length of the inverse automorphism in the case that it is unitriangular.      20. Factorization in K[Xn,Xn+1,…,X2n−1]      David F. Anderson  Susanne Jenkens 《代数通讯》2013,41(7):2561-2576

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

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.     

On the groups of unitriangular automorphisms of relatively free groups

We describe the structure of the group U _n of unitriangular automorphisms of the relatively free group G _n of finite rank n in an arbitrary variety C of groups. This enables us to introduce an effective concept of normal form for the elements and present U _n by using generators and defining relations. The cases n = 1, 2 are obvious: U ₁ is trivial, and U ₂ is cyclic. For n ?? 3 we prove the following: If G _n?1 is a nilpotent group then so is U _n . If G _n?1 is a nilpotent-by-finite group then U _n admits a faithful matrix representation. But if the variety C is different from the variety of all groups and G _n?1 is not nilpotent-by-finite then U _n admits no faithful matrix representation over any field. Thus, we exhaustively classify linearity for the groups of unitriangular automorphisms of finite rank relatively free groups in proper varieties of groups, which complements the results of Olshanskii on the linearity of the full automorphism groups AutG _n . Moreover, we introduce the concept of length of an automorphism of an arbitrary relatively free group G _n and estimate the length of the inverse automorphism in the case that it is unitriangular.