Primitives and central detection numbers in group cohomology

Fix a prime p. Given a finite group G, let H^∗(G) denote its mod p cohomology. In the early 1990s, Henn, Lannes, and Schwartz introduced two invariants d₀(G) and d₁(G) of H^∗(G) viewed as a module over the mod p Steenrod algebra. They showed that, in a precise sense, H^∗(G) is respectively detected and determined by Hd(CG(V)) for d?d₀(G) and d?d₁(G), with V running through the elementary abelian p-subgroups of G.The main goal of this paper is to study how to calculate these invariants. We find that a critical role is played by the image of the restriction of H^∗(G) to H^∗(C), where C is the maximal central elementary abelian p-subgroup of G. A measure of this is the top degree e(G) of the finite dimensional Hopf algebra H^∗(C)_⊗H^∗(G)Fp, a number that tends to be quite easy to calculate.Our results are complete when G has a p-Sylow subgroup P in which every element of order p is central. Using the Benson-Carlson duality, we show that in this case, d₀(G)=d₀(P)=e(P), and a similar exact formula holds for d₁. As a bonus, we learn that He(G)(P) contains nontrivial essential cohomology, reproving and sharpening a theorem of Adem and Karagueuzian.In general, we are able to show that d₀(G)?max{e(CG(V))|V<G} if certain cases of Benson's Regularity Conjecture hold. In particular, this inequality holds for all groups such that the difference between the p-rank of G and the depth of H^∗(G) is at most 2. When we look at examples with p=2, we learn that d₀(G)?14 for all groups with 2-Sylow subgroup of order up to 64, with equality realized when G=SU(3,4).En route we study two objects of independent interest. If C is any central elementary abelian p-subgroup of G, then H^∗(G) is an H^∗(C)-comodule, and we prove that the subalgebra of H^∗(C)-primitives is always Noetherian of Krull dimension equal to the p-rank of G minus the p-rank of C. If the depth of H^∗(G) equals the rank of Z(G), we show that the depth essential cohomology of G is nonzero (reproving and extending a theorem of Green), and Cohen-Macauley in a certain sense, and prove related structural results.     

Weak sense of direction labelings and graph embeddings

An edge-labeling λ for a directed graph G has a weak sense of direction (WSD) if there is a function f that satisfies the condition that for any node u and for any two label sequences α and α^′ generated by non-trivial walks on G starting at u, f(α)=f(α^′) if and only if the two walks end at the same node. The function f is referred to as a coding function of λ. The weak sense of direction number of G, WSD(G), is the smallest integer k so that G has a WSD-labeling that uses k labels. It is known that WSD(G)≥Δ⁺(G), where Δ⁺(G) is the maximum outdegree of G.Let us say that a function τ:V(G)→V(H) is an embedding from G onto H if τ demonstrates that G is isomorphic to a subgraph of H. We show that there are deep connections between WSD-labelings and graph embeddings. First, we prove that when f_H is the coding function that naturally accompanies a Cayley graph H and G has a node that can reach every other node in the graph, then G has a WSD-labeling that has f_H as a coding function if and only if G can be embedded onto H. Additionally, we show that the problem “Given G, does G have a WSD-labeling that uses a particular coding function f?” is NP-complete even when G and f are fairly simple.Second, when D is a distributive lattice, H(D) is its Hasse diagram and G(D) is its cover graph, then WSD(H(D))=Δ⁺(H(D))=d^∗, where d^∗ is the smallest integer d so that H(D) can be embedded onto the d-dimensional mesh. Along the way, we also prove that the isometric dimension of G(D) is its diameter, and the lattice dimension of G(D) is Δ⁺(H(D)). Our WSD-labelings are poset-based, making use of Birkhoff’s characterization of distributive lattices and Dilworth’s theorem for posets.     

On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

The monotone asymmetric travelling salesman polytope P?ⁿ_T is defined to be the convex hull of the incidence vectors of all hamiltonian circuits and all subsets of these in a complete diagraph of order n. We prove that certain hypohamiltonian diagraphs G=(V,E), i.e. diagraphs which are not hamiltonian but such that G–υ is hamiltonian for all υ?V, induce facets x(E)?n–1 of P?ⁿ_T. This result indicates that P?ⁿ_T has very complicated facets and that it is very unlikely that an explicit complete characterization of P?ⁿ_T can ever be given.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

Domains with growth conditions for the quasihyperbolic metric

For a given growth functionH, we say that a domainD ?R ⁿ is anH-domain if δ_D x≤δ_D(x ₀)H(k _D(x,x ₀)),x ∈D, where δ_D(x)=d(x?D) andk _D denotes the quasihyperbolic distance. We show that ifH satisfiesH(0)=1, |H'|≤H, andH"≤H, then there exists an extremalH-domain. Using this fact, we investigate some fundamental properties ofH-domains.     

The Hosoya polynomial decomposition for catacondensed benzenoid graphs

For a graph G with the vertex set V(G), we denote by d(u,v) the distance between vertices u and v in G, by d(u) the degree of vertex u. The Hosoya polynomial of G is H(G)=∑_{u,v}⊆V(G)x^d(u,v). The partial Hosoya polynomials of G are for positive integer numbers m and n. It is shown that H(G₁)−H(G₂)=x²(x+1)²(H₃₃(G₁)−H₃₃(G₂)),H₂₂(G₁)−H₂₂(G₂)=(x²+x−1)²(H₃₃(G₁)−H₃₃(G₂)) and H₂₃(G₁)−H₂₃(G₂)=2(x²+x−1)(H₃₃(G₁)−H₃₃(G₂)) for arbitrary catacondensed benzenoid graphs G₁ and G₂ with equal number of hexagons. As an application, we give an affine relationship between H(G) with two other distance-based polynomials constructed by Gutman [I. Gutman, Some relations between distance-based polynomials of trees, Bulletin de l’Académie Serbe des Sciences et des Arts (Cl. Math. Natur.) 131 (2005) 1-7].     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

On the localization of binding for Schrödinger operators and its extension to elliptic operators

In this paper we study the asymptotic behavior of the ground state energyE(R) of the Schrödinger operatorP _R=?Δ+V ₁(x)+V ₂(x-R),x,R ∈?ⁿ, where the potentialsV _i are small perturbations of the Laplacian in ?ⁿ,n≥3. The methods presented here apply also in the investigation of the ground state energyE(g) of the operatorPg=P+V ₁(x)+V ₂(gx), x ∈X,g ∈G, whereP _g is an elliptic operator which is defined on a noncompact manifoldX, G is a discrete group acting onX by diffeomorphismsG×X∈(g, x)→gx∈X, andP is aG-invariant elliptic operator which is subcritical inX.     

Sharp bounds of the zeroth-order general Randi? index of bicyclic graphs with given pendent vertices

Let G be a simple connected graph and α be a given real number. The zeroth-order general Randi? index of ⁰R_α(G) is defined as ∑_v∈V(G)[d_G(v)]^α, where d_G(v) denotes the degree of the vertex v of G. In this paper, for any α(≠0,1), we give sharp bounds of the zeroth-order general Randi? index ⁰R_α of all bicyclic graphs with n vertices and k pendent vertices.     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

More on “Connected (n, m)-graphs with minimum and maximum zeroth-order general Randi? index”

Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index ⁰R_α(G) of the graph G is defined as ∑_u∈V(G)d(u)^α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize ¹ for α<0 the connected G(n,m)-graphs with maximum value ⁰R_α(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.     

Orientation distance graphs

For two nonisomorphic orientations D and D′ of a graph G, the orientation distance d_o(D,D′) between D and D′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D′. The orientation distance graph 𝒟_o(G) of G has the set 𝒪(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D′ of 𝒟₀(G) are adjacent if and only if d_o(D,D′) = 1. For a nonempty subset S of 𝒪(G), the orientation distance graph 𝒟₀(S) of S is the induced subgraph 〈S〉 of 𝒟_o(G). A graph H is an orientation distance graph if there exists a graph G and a set S⊆ 𝒪(G) such that 𝒟_o(S) is isomorphic to H. In this case, H is said to be an orientation distance graph with respect to G. This paper deals primarily with orientation distance graphs with respect to paths. For every integer n ≥ 4, it is shown that 𝒟_o(P_n) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n ≥ 3 the clique number of 𝒟_o(P_n) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001     

Quasirecognition by prime graph of 2 D n (3α) where n = 4m + 1 ≥ 21 and α is odd

Let G be a finite group. The prime graph of G is denoted by Γ(G). In this paper, as the main result, we show that if G is a finite group such that Γ(G) = Γ(² D _n (3^α)), where n = 4m+ 1 and α is odd, then G has a unique non-Abelian composition factor isomorphic to ² D _n (3^α). We also show that if G is a finite group satisfying |G| = |² D _n (3^α)|, and Γ(G) = Γ(² D _n (3^α)), then G ? ² D _n (3^α). As a consequence of our result, we give a new proof for a conjecture of Shi and Bi for ² D _n (3^α). Application of this result to the problem of recognition of finite simple groups by the set of element orders are also considered. Specifically, it is proved that ² D _n (3^α) is quasirecognizable by the spectrum.     

Trees with second minimum general Randić index for α>0

The general Randi? index R _α (G) of a graph G is the sum of the weights (d(u)d(v)) ^α of all edges uv of G, where α is a real number(α≠0) and d(u) denotes the degree of the vertex u. We have known that P _n has minimum general Randi? index for α>0 among trees when n≥5. In this paper, we prove that P _n,3 has second minimum general Randi? index for α>0 among trees when n≥7.     

Intersection theorems for group divisible difference sets

Let D be an (m,n;k;λ₁,λ₂)-group divisible difference set (GDDS) of a group G, written additively, relative to H, i.e. D is a k-element subset of G, H is a normal subgroup of G of index m and order n and for every nonzero element g of G,?{(d₁,d₂)?,d₁,d₂?D,d₁?d₂=g}? is equal to λ₁ if g is in H, and equal to λ₂ if g is not in H. Let H₁,H₂,…,H_m be distinct cosets of H in G and S_i=D∩H_i for all i=1,2,…,m. Some properties of S₁,S₂,…,S_m are studied here. Table 1 shows all possible cardinalities of S_i's when the order of G is not greater than 50 and not a prime. A matrix characterization of cyclic GDDS's with λ₁=0 implies that there exists a cyclic affine plane of even order, say n, only if n is divisible by 4 and there exists a cyclic (n?1,$\text{1}\text{2}$n?1,$\text{1}\text{4}$n?1)-difference set.     

Efficient Algorithms for Finding a Core of a Tree with a Specified Length

Acoreof a graphGis a pathPinGthat is central with respect to the property of minimizingd(P)=∑_v∈V(G)d(v, P), whered(v, P) is the distance from vertexvto pathP. This paper presents efficient algorithms for finding a core of a tree with a specified length. The sequential algorithm runs inO(n log n) time, wherenis the size of the tree. The parallel algorithm runs inO(log²n) time usingO(n) processors on an EREW PRAM model.