Hamilton Decomposable Graphs with Specified Leaves

In this paper, a simple proof is given of a result that provides necessary and sufficient conditions for the existence of a hamilton decomposition of G–E(H) for any non-bipartite r-regular complete multipartite graph G and for any 2-factor H of G. Such conditions were originally obtained by Buchanan for complete graphs (ie when r=|V(G)|–1), and in some cases by Leach and Rodger otherwise (Leach and Rodger also settled the bipartite case). This result is extended to consider hamilton decompositions of G–E(HF), where F is a 1-factor of G.     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday     

The vertex-cover polynomial of a graph

In this paper we define the vertex-cover polynomial Ψ(G,τ) for a graph G. The coefficient of τ^r in this polynomial is the number of vertex covers V′ of G with |V′|=r. We develop a method to calculate Ψ(G,τ). Motivated by a problem in biological systematics, we also consider the mappings f from {1, 2,…,m} into the vertex set V(G) of a graph G, subject to f⁻¹(x)f⁻¹(y)≠ for every edge xy in G. Let F(G,m) be the number of such mappings f. We show that F(G,m) can be determined from Ψ(G,τ).     

Extending the multivariate generalised and generalised distributions

The GGH family of multivariate distributions is obtained by scale mixing on the Exponential Power distribution using the Extended Generalised Inverse Gaussian distribution. The resulting GGH family encompasses the multivariate generalised hyperbolic (GH), which itself contains the multivariate t and multivariate Variance-Gamma (VG) distributions as special cases. It also contains the generalised multivariate t distribution [O. Arslan, Family of multivariate generalised t distribution, Journal of Multivariate Analysis 89 (2004) 329–337] and a new generalisation of the VG as special cases. Our approach unifies into a single GH-type family the hitherto separately treated t-type [O. Arslan, A new class of multivariate distribution: Scale mixture of Kotz-type distributions, Statistics and Probability Letters 75 (2005) 18–28; O. Arslan, Variance–mean mixture of Kotz-type distributions, Communications in Statistics-Theory and Methods 38 (2009) 272–284] and VG-type cases. The GGH distribution is dual to the distribution obtained by analogous mixing on the scale parameter of a spherically symmetric stable distribution. Duality between the multivariate t and multivariate VG [S.W. Harrar, E. Seneta, A.K. Gupta, Duality between matrix variate t and matrix variate V.G. distributions, Journal of Multivariate Analysis 97 (2006) 1467–1475] does however extend in one sense to their generalisations.     

Certain Homology Cycles of the Independence Complex of Grids

Let G be an infinite graph such that the automorphism group of G contains a subgroup K ?? ^d with the property that G/K is finite. We examine the homology of the independence complex Σ(G/I) of G/I for subgroups I of K of full rank, focusing on the case that G is the square, triangular, or hexagonal grid. Specifically, we look for a certain kind of homology cycles that we refer to as “cross-cycles,” the rationale for the terminology being that they are fundamental cycles of the boundary complex of some cross-polytope. For the special cases just mentioned, we determine the set Q(G,K) of rational numbers r such that there is a group I with the property that Σ(G/I) contains cross-cycles of degree exactly r?|G/I|?1; |G/I| denotes the size of the vertex set of G/I. In each of the three cases, Q(G,K) turns out to be an interval of the form [a,b]∩?={r∈?:a≤r≤b}. For example, for the square grid, we obtain the interval $[\frac{1}{5},\frac{1}{4}]\cap \mathbb{Q}Let G be an infinite graph such that the automorphism group of G contains a subgroup K ≅ℤ ^d with the property that G/K is finite. We examine the homology of the independence complex Σ(G/I) of G/I for subgroups I of K of full rank, focusing on the case that G is the square, triangular, or hexagonal grid. Specifically, we look for a certain kind of homology cycles that we refer to as “cross-cycles,” the rationale for the terminology being that they are fundamental cycles of the boundary complex of some cross-polytope. For the special cases just mentioned, we determine the set Q(G,K) of rational numbers r such that there is a group I with the property that Σ(G/I) contains cross-cycles of degree exactly r⋅|G/I|−1; |G/I| denotes the size of the vertex set of G/I. In each of the three cases, Q(G,K) turns out to be an interval of the form [a,b]∩ℚ={r∈ℚ:a≤r≤b}. For example, for the square grid, we obtain the interval [\frac15,\frac14]?\mathbbQ[\frac{1}{5},\frac{1}{4}]\cap \mathbb{Q}.     

The Ramsey property for graphs with forbidden complete subgraphs

The following theorem is proved: Let G be a finite graph with cl(G) = m, where cl(G) is the maximum size of a clique in G. Then for any integer r ≥ 1, there is a finite graph H, also with cl(H) = m, such that if the edges of H are r-colored in any way, then H contains an induced subgraph G′ isomorphic to G with all its edges the same color.     

The Virtual Poincaré Polynomials of Homogeneous Spaces

We factor the virtual Poincaré polynomial of every homogeneous space G/H, where G is a complex connected linear algebraic group and H is an algebraic subgroup, as t^2u (t²–1)^r Q_G/H(t²) for a polynomial Q_G/H with nonnegative integer coefficients. Moreover, we show that Q_G/H(t²) divides the virtual Poincaré polynomial of every regular embedding of G/H, if H is connected.     

A note on 1-factors in graphs

Conditions on a graphG are presented which are sufficient to guarantee thatG–Z contains a 1-factor, whereZ is a set of edges ofG of restricted cardinality. These conditions provide generalizations of several known results and, further, establish the result that ifG is anr-regular, (r–2)-edge-connected graph (r2) of even order andz is an integer with 0zr–1 such thatG contains fewer thanr–z edge cut sets of cardinalityr–2, thenG–Z has a 1-factor for each setZ ofz edges ofG.     

Primes and Right Ideals in Right Cones

A right cone H in a group G is a submonoid of G that generates G and aH ? bH for a, b ? H implies bH ? aH. With any right ideal I ≠ H of H a completely prime ideal P _r (I) of H is associated and the set 𝒫(I) of right ideals I′ of H with the same associated prime ideal P′ =P _r (I) is determined if P′·? P″ is a right invariant segment in H. The set 𝒫(I) is also described if P _r (I) is a limit prime.     

Graphs with Least Eigenvalue −2: The Star Complement Technique

Let G be a connected graph with least eigenvalue –2, of multiplicity k. A star complement for –2 in G is an induced subgraph H = G – X such that |X| = k and –2 is not an eigenvalue of H. In the case that G is a generalized line graph, a characterization of such subgraphs is used to decribe the eigenspace of –2. In some instances, G itself can be characterized by a star complement. If G is not a generalized line graph, G is an exceptional graph, and in this case it is shown how a star complement can be used to construct G without recourse to root systems.     

Upper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) =IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

On αrγs(k)-perfect graphs

For some integer k0 and two graph parameters π and τ, a graph G is called πτ(k)-perfect, if π(H)−τ(H)k for every induced subgraph H of G. For r1 let α_r and γ_r denote the r-(distance)-independence and r-(distance)-domination number, respectively. In (J. Graph Theory 32 (1999) 303–310), I. Zverovich gave an ingenious complete characterization of α₁γ₁(k)-perfect graphs in terms of forbidden induced subgraphs. In this paper we study α_rγ_s(k)-perfect graphs for r,s1. We prove several properties of minimal α_rγ_s(k)-imperfect graphs. Generalizing Zverovich's main result in (J. Graph Theory 32 (1999) 303–310), we completely characterize α_2r−1γ_r(k)-perfect graphs for r1. Furthermore, we characterize claw-free α₂γ₂(k)-perfect graphs.     

Cohen–Macaulay Multi–Rees Algebras

Let A be a local ring, and let I ₁,...,I _r A be ideals of positive height. In this article we compare the Cohen–Macaulay property of the multi–Rees algebra R _A (I ₁,...,I _r ) to that of the usual Rees algebra R _A (I ₁ ··· I _r ) of the product I ₁ ··· I _r . In particular, when the analytic spread of I ₁ ··· I _r is small, this leads to necessary and sufficient conditions for the Cohen–Macaulayness of R _A (I ₁,...,I _r ). We apply our results to the theory of joint reductions and mixed multiplicities.     

Generic Stability and Essential Components of Generalized KKM Points and Applications

We propose the definition of T-KKM points and consider generic stability of T-KKM mappings and essential components of sets of T-KKM points. As applications, using a unified approach, we derive from these results the existence of essential components of solution sets to various optimization-related problems. We do this in two steps. First, we deduce the corresponding results for variational inclusions, which are new. Then we obtain, as consequences, the existence of essential components of solutions to other problems, which are new or include recent ones in the literature.     

Continuity in G

For a discrete group G, we consider βG, the Stone– ech compactification of G, as a right topological semigroup, and G^*=βGG as a subsemigroup of βG. We study the mappings λ_p^* :G^*→G^*and μ^* :G^*→G^*, the restrictions to G^* of the mappings λ_p :βG→βG and μ :βG→βG, defined by the rules λ_p(q)=pq, μ(q)=qq. Under some assumptions, we prove that the continuity of λ_p^* or μ^* at some point of G^* implies the existence of a P-point in ω^*.     

On Units of Group Algebras of 2-Groups of Maximal Class

Abstract

We determine the number of elements of order two in the group of normalized units V(𝔽₂ G) of the group algebra 𝔽₂ G of a 2-group of maximal class over the field 𝔽₂ of two elements. As a consequence for the 2-groups G and H of maximal class we have that V(𝔽₂ G) and V(𝔽₂ H) are isomorphic if and only if G and H are isomorphic.     

Parameterized graph cleaning problems

We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference |V(G)|−|V(H)| with H and G being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We show fixed-parameter tractability of the cases where both H and G are planar and H is 3-connected, or H is a tree and G is arbitrary. We also prove that the problem when H and G are both 3-connected planar graphs is NP-complete without parameterization.     

The 0–1 inverse maximum stable set problem

In this paper we study the 0–1 inverse maximum stable set problem, denoted by IS_{0,1}. Given a graph and a fixed stable set, it is to delete the minimum number of vertices to make this stable set maximum in the new graph. We also consider IS_{0,1} against a specific algorithm such as Greedy and 2opt, aiming to delete the minimum number of vertices so that the algorithm selects the given stable set in the new graph; we denote them by IS_{0,1},greedy and IS_{0,1},2opt, respectively. Firstly, we show that they are NP-hard, even if the fixed stable set contains only one vertex. Secondly, we achieve an approximation ratio of for IS_{0,1},2opt. Thirdly, we study the tractability of IS_{0,1} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of IS_{0,1} and IS_{0,1},2opt for some other classes of graphs.