A characterization of planar cubic graphs

If S is a collection of circuits in a graph G, the circuits in S are said to be consistently orientable if G can be oriented so that they are all directed circuits. If S is a set of three or more consistently orientable circuits such that no edge of G belongs to more than two circuits of S, then S is called a ring if there exists a cyclic ordering C₀, C₁,…, C_{n ? 1}, C₀ of the n circuits in S such that $\text{EC}{}_{\mathrm{i}}\text{? EC}{}_{\mathrm{j}}\text{≠ ?}$ if and only if j = i or j ≡ i ? 1 (mod n) or j ≡ i + 1 (mod n). We characterise planar cubic graphs in terms of the non-existence of a ring with certain specified properties.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

Simultaneous weighted sums of elements of finitely generated multiplicative groups

Let {G_j}_jεJ be a finite set of finitely generated subgroups of the multiplicative group of complex numbers C^x. Write H=∩ _jεJ G_j. Let n be a positive integer and a_ij a complex number for i = 1, ..., n and j ε J. Then there exists a set W with the following properties. The cardinality of W depends only on {G_j}_jεJ and n. If, for each jεJ, α has a representation α = Σ _iⁿ = ₁a _ijg_ij in elements g_ij of G_j, then α has a representation a= Σ_k=1ⁿ w_kh_k with w_kεW, h_k εH for k = 1,..., n. The theorem in this note gives information on such representations.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

On geometric convergence of discrete groups

One of the basic questions in the Kleinian group theory is to understand both algebraic and geometric limiting behavior of sequences of discrete subgroups. In this paper we consider the geometric convergence in the setting of the isometric group of the real or complex hyperbolic space. It is known that if Γ is a non-elementary finitely generated group and ? _i : Γ → SO(n, 1) a sequence of discrete and faithful representations, then the geometric limit of ? _i (Γ) is a discrete subgroup of SO(n, 1). We generalize this result by showing that for a sequence of discrete and non-elementary subgroups {G _j } of SO(n, 1) or PU(n, 1), if {G _j } has uniformly bounded torsion, then its geometric limit is either elementary, or discrete and non-elementary.     

A counter example for nilpotent groups

Let R be a ring with 1, I be a nilpotent subring of R (there exists a natural number n, such that In = 0), and I be generated by {xj |j ∈ J} as ring. Write U = 1 + I, and it is a nilpotent group with class ≤ n - 1. Let G be the subgroup of U which is generated by {1 + xj|j ∈ J}. The group constructed in this paper indicates that the nilpotency class of G can be less than that of U.     

Partitioning graphs into complete and empty graphs

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

On mutually permutable products of finite groups

We say that the subgroups G ₁ and G ₂ of a group G are mutually permutable if G ₁ permutes with every subgroup of G ₂ and G ₂ permutes with every subgroup of G ₁. Let G=G ₁ G ₂…G _n be the product of its pairwise permutable subgroups G ₁,G ₂,…,G _n such that the product G _i G _j is mutually permutable. We investigate the structure of the finite group G if special properties of the factors G ₁,G ₂,…,G _n are known. Our results improve and extend some results of Asaad and Shaalan [1], Ezquerro and Soler-Escrivà [9] and Asaad and Monakhov [3].     

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).     

[r,s,t]-Coloring of K n,n

Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v _i )?c(v _j )|≥r for every two adjacent vertices v _i ,v _j , |c(e _i )?c(e _j )|≥s for every two adjacent edges e _i ,e _j , and |c(v _i )?c(e _j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ _r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ _r,s,t (K _n,n ) in all cases.     

The Heyde theorem for locally compact Abelian groups

We prove a group analogue of the well-known Heyde theorem where a Gaussian measure is characterized by the symmetry of the conditional distribution of one linear form given another. Let X be a locally compact second countable Abelian group containing no subgroup topologically isomorphic to the circle group T, G be the subgroup of X generated by all elements of order 2, and Aut(X) be the set of all topological automorphisms of X. Let αj,βj∈Aut(X), j=1,2,…,n, n?2, such that for all i≠j. Let ξj be independent random variables with values in X and distributions μj with non-vanishing characteristic functions. If the conditional distribution of L₂=β₁ξ₁+?+βnξn given L₁=α₁ξ₁+?+αnξn is symmetric, then each μj=γj∗ρj, where γj are Gaussian measures, and ρj are distributions supported in G.     

Homology of certain algebras defined by graphs

Let K(G) for a finite graph G with vertices v₁,...,v_n denote the K-algebra with generators X₁,...,X_n and defining relations X_iX_j=X_jX_i if and only if v_i is not connected to v_j by an edge in G. We describe centralizers of monomials, show that the centralizer of a monomial is again a graph algebra, prove a unique factorization theorem for factorizations of monomials into commuting factors, compute the homology of K(G), and show that K(G) is the homology ring of a certain loop space. We also construct a K(π, 1) explicitly where π is the group with generators X₁,...,X_n and defining relations X_iX_j=X_jX_i if and only if v_i is not connected to v_j by an edge in G.     

On groups factorizable in commuting almost locally normal subgroups

We prove that anRN-group (in particular, locally solvable)G =G ₁ G ₂ ...G _n withG _i and π(G _i ) ∩ π(G _j ) = ?,i ≠j is a periodic hyper-Abelian group if the subgroupsG _j are almost locally normal.     

Degree sequence and supereulerian graphs

A sequence d=(d₁,d₂,…,d_n) is graphic if there is a simple graph G with degree sequence d, and such a graph G is called a realization of d. A graphic sequence d is line-hamiltonian if d has a realization G such that L(G) is hamiltonian, and is supereulerian if d has a realization G with a spanning eulerian subgraph. In this paper, it is proved that a nonincreasing graphic sequence d=(d₁,d₂,…,d_n) has a supereulerian realization if and only if d_n≥2 and that d is line-hamiltonian if and only if either d₁=n−1, or ∑_di=1d_i≤∑_dj≥2(d_j−2).     

Graphs without K4 and well-quasi-ordering

It is proved that given an infinite sequence G₁, G₂, G₃,…, of series-parallel graphs there are indices i < j such that G_j contains an induced subgraph contractable onto G_i. An example is given showing that for planar graphs the preceding theorem fails.     

Perfect matchings in random intersection graphs

Let W ₁,??,W _n be independent random subsets of [m]={1,??,m}. Assuming that each W _i is uniformly distributed in the class of d-subsets of?[m] we study the uniform random intersection graph G _s (n,m,d) on the vertex set {W ₁,??W _n }, defined by the adjacency relation: W _i ??W _j whenever |W _i ??W _j |?Rs. For even?n we show that as n,m???? the edge density threshold for the property that G _s (n,m,d) contains a perfect matching is asymptotically the same as that for G _s (n,m,d) being connected.     

Maximum generic nullity of a graph

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree.     

Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

Two characterizations of interchange graphs of complete m-partite graphs

A graph G is m-partite if its points can be partitioned into m subsets V₁,…,V_m such that every line joins a point in V_i with a point in V_j, i ≠ j. A complete m-partite graph contains every line joining V_i with V_j. A complete graph K_p has every pair of its p points adjacent. The nth interchange graph I_n(G) of G is a graph whose points can be identified with the K_n+1's of G such that two points are adjacent whenever the corresponding K_n+1's have a K_n in common.Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete m-partite graphs for m ≥ 2.