The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.     

Waiting-time tail probabilities in queues with long-tail service-time distributions

We consider the standardGI/G/1 queue with unlimited waiting room and the first-in first-out service discipline. We investigate the steady-state waiting-time tail probabilitiesP(W>x) when the service-time distribution has a long-tail distribution, i.e., when the service-time distribution fails to have a finite moment generating function. We have developed algorithms for computing the waiting-time distribution by Laplace transform inversion when the Laplace transforms of the interarrival-time and service-time distributions are known. One algorithm, exploiting Pollaczek's classical contourintegral representation of the Laplace transform, does not require that either of these transforms be rational. To facilitate such calculations, we introduce a convenient two-parameter family of long-tail distributions on the positive half line with explicit Laplace transforms. This family is a Pareto mixture of exponential (PME) distributions. These PME distributions have monotone densities and Pareto-like tails, i.e., are of orderx ^–r forr>1. We use this family of long-tail distributions to investigate the quality of approximations based on asymptotics forP(W>x) asx. We show that the asymptotic approximations with these long-tail service-time distributions can be remarkably inaccurate for typicalx values of interest. We also derive multi-term asymptotic expansions for the waiting-time tail probabilities in theM/G/1 queue. Even three terms of this expansion can be remarkably inaccurate for typicalx values of interest. Thus, we evidently must rely on numerical algorithms for determining the waiting-time tail probabilities in this case. When working with service-time data, we suggest using empirical Laplace transforms.     

Computing 2-cocyeles for central extensions and relative difference sets

We present an algorithm to compute H ²(G,U) for a finite group G and finite abelian group U (trivial G-module). The algorithm returns a generating set for the second cohomology group in terms of representative 2-cocycles, which are given explicitly. This information may be used to find presentations for corresponding central extensions of U by G. An application of the algorithm to the construction of relative (4t, 2,4t, 2t) -difference sets is given.     

Projective supercharacter theory

Abstract

The idea of supercharacters for ordinary characters of a finite group G was introduced by Diaconis and Isaacs and further extended to Brauer characters by Chen and Lewis. The twin concepts of supercharacters and superclasses are further extended here to α-characters of G for α a complex-valued 2-cocycle of G. An α-quasi-supercharacter theory of G arises when the set of α-quasi-supercharacters of G are compatible with the set of α-regular quasi-superclasses of G. The structure of solvable groups that have exactly two α-quasi-supercharacter theories is determined.

Communicated by Mark L. Lewis     

Lamron ℓ-groups

The article introduces a new class of lattice-ordered groups. An ?-group G is lamron if Min(G)^?1 is a Hausdorff topological space, where Min(G)^?1 is the space of all minimal prime subgroups of G endowed with the inverse topology. It will be evident that lamron ?-groups are related to ?-groups with stranded primes. In particular, it is shown that for a W-object (G,u), if every value of u contains a unique minimal prime subgroup, then G is a lamron ?-group; such a W-object will be said to have W-stranded primes. A diverse set of examples will be provided in order to distinguish between the notions of lamron, stranded primes, W-stranded primes, complemented, and weakly complemented ?-groups.     

Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.     

A characterization of the one parameter exponential family of distributions by monotonicity of likelihood ratios

Summary Any one parameter exponential family of distributions has monotone likelihood ratios. As the product probabilities of n identical distributions of an exponential family form again an exponential family, it has monotone likelihood ratios for arbitrary n. Furthermore, the members of an exponential family are mutually absolutely continuous. In Part 1, we show that these properties uniquely characterize the exponential family. The application of this result to the theory of testing hypotheses (Part 2) shows that if a family of mutually absolutely continuous distributions has uniformly most powerful tests for arbitrary levels of significance, and arbitrary sample sizes, then it is necessarily an exponential family.The research was done while this author was a Visiting Professor in the Department of Statistics at the University of Chicago. It was supported by Research Grants Nos. NSF-G10368 and NSF-G21058 from the Division of Mathematical, Physical and Engineering Sciences of the National Science Foundation.     

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.     

Connected Domination Stable Graphs Upon Edge Addition

Abstract

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.     

Degree Graphs of Simple Groups of Exceptional Lie Type

Abstract

Let G be a finite group and let cd(G) be the set of irreducible character degrees of G. The degree graph Δ(G) of G is the graph whose set of vertices is the set of primes that divide degrees in cd(G), with an edge between p and q if pq divides a for some degree a ∈ cd(G). In this paper, we determine the graph Δ(G) when G is a finite simple group of exceptional Lie type.     

Matroidal families of finite connected nonhomeomorphic graphs exist

A matroidal family is a nonempty set ? of connected finite graphs such that for every arbitrary finite graph G the edge sets of the subgraphs of G which are isomorphic to an element of ? form a matroid on the edge set of G. In the present paper the question whether there are any matroidal families besides the four previously described by Simões-Pereira is answered affirmatively. It is shown that for every natural number n ? 2 there is a matroidal family that contains the complete graph with n vertices. For n = 4 this settles Simões-Pereira's conjecture that there is a matroidal family containing all wheels.     

Type G Distributions on {\mathbb{R}} d

This paper presents a systematic study of the class of multivariate distributions obtained by a Gaussian randomization of jumps of a Lévy process. This class, called the class of type G distributions, constitutes a closed convolution semigroup of the family of symmetric infinitely divisible probability measures. Spectral form of Lévy measures of type G distributions is obtained and it is shown that type G property can not be determined by one dimensional projections. Conditionally Gaussian structure of type G random vectors is exhibited via series representations.     

Orthogonal latin square graphs

An orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. If G is an arbitrary finite graph, we say that G is realizable as an OLSG if there is an OLSG isomorphic to G. The spectrum of G [Spec(G)] is defined as the set of all integers n that there is a realization of G by latin squares of order n. The two basic theorems proved here are (1) every graph is realizable and (2) for any graph G, Spec G contains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a given n lies in the spectrum.     

Growth tightness for word hyperbolic groups

We show that non-elementary word hyperbolic groups are growth tight. This means that, given such a group G and a finite set A of its generators, for any infinite normal subgroup N of G, the exponential growth rate of G/N with respect to the natural image of A is strictly less than the exponential growth rate of G with respect to A. Received: 20 September 2001; in final form: 24 January 2002/ Published online: 5 September 2002 The work has been supported by the Swiss National Science Foundation. The second author has been supported also by INTAS, grant No. 97–1259     

Modules over group rings of soluble groups with a certain condition of maximality

Let A be an R G-module, where R is an integral domain and G is a soluble group. Suppose that C _G (A) = 1 and A/C _A (G) is not a noetherian R-module. Let L _nnd(G) be the family of all subgroups H of G such that A/C _A (H) is not a noetherian R-module. In this paper we study the structure of those G for which L _nnd(G) satisfies the maximal condition.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Induced Matching Extendable Graph Powers

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. We obtain the following two results which give positive answers to two conjectures of Yuan. Result 1. If a connected graph G with |V(G)| even is locally connected, then G² is strongly IM-extendable. Result 2. If G is a 2-connected graph with |V(G)| even, then G³ is strongly IM-extendable. Research Supported by NSFC Fund 10371102.     

Subset selection procedures for restricted families of probability distributions

In this paper we are interested in studying multiple decision procedures fork (k≧2) populations which are themselves unknown but which one assumed to belong to a restricted family. We propose to study a selection procedure for distributions associated with these populations which are convex-ordered with respect to a specified distributionG assuming that there exists a best one. The procedure described here is based on a statistic which is a linear function of the firstr order statistics and which reduces to the total life statistics whenG is exponential. The infimum of the probability of a correct selection and an asymptotic expression for this probability are obtained using the subset selection approach. Some other properties of this procedure are discussed. Asymptotic relative efficiencies of this rule with respect to some selection procedures proposed by Barlow and Gupta [3] for the star-ordered distributions and by Gupta [8] for the gamma populations with known shape parameters are obtained. A selection procedure for selecting the best population using the indifference zone approach is also studied. This research was supported by the Office of Naval Research Contract N00014-75-C-0455 at Purdue University. Reproduction in whole or in part is permitted for any purpose of the United States Government. Ming-Wei Lu is now at the Department of Vital and Health Statistics, Michigan.     

Constraints on the number of maximal independent sets in graphs

A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. Let i(G) denote the number of maximal independent sets of G. Here, we prove two conjectures, suggested by P. Erdös, that the maximum number of maximal independent sets among all graphs of order n in a family Φ is o(3^n/3) if Φ is either a family of connected graphs such that the largest value of maximum degrees among all graphs of order n in Φ is o(n) or a family of graphs such that the approaches infinity as n → ∞.