Roots of Independence Polynomials of Well Covered Graphs

Let G be a well covered graph, that is, all maximal independent sets of G have the same cardinality, and let i_k denote the number of independent sets of cardinality k in G. We investigate the roots of the independence polynomial i(G, x) = i_kx^k. In particular, we show that if G is a well covered graph with independence number , then all the roots of i(G, x) lie in in the disk |z| (this is far from true if the condition of being well covered is omitted). Moreover, there is a family of well covered graphs (for each ) for which the independence polynomials have a root arbitrarily close to –.     

Uniformly Packed Codes and More Distance Regular Graphs from Crooked Functions

Let V and W be n-dimensional vector spaces over GF(2). A function Q : V W is called crooked (a notion introduced by Bending and Fon-Der-Flaass) if it satisfies the following three properties:

Recursive weighted treelike networks

We propose a geometric growth model for weighted scale-free networks, which is controlled by two tunable parameters. We derive exactly the main characteristics of the networks, which are partially determined by the parameters. Analytical results indicate that the resulting networks have power-law distributions of degree, strength, weight and betweenness, a scale-free behavior for degree correlations, logarithmic small average path length and diameter with network size. The obtained properties are in agreement with empirical data observed in many real-life networks, which shows that the presented model may provide valuable insight into the real systems.     

Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces

In this paper we obtain the equivalence of the Gromov hyperbolicity between an extensive class of complete Riemannian surfaces with pinched negative curvature and certain kind of simple graphs, whose edges have length 1, constructed following an easy triangular design of geodesics in the surface.     

Asymptotic exponential cones of Metzler matrices and their use in the solution of an algebraic problem

The aim of this paper is that of investigating the asymptotic exponential cone of a single Metzler matrix, introduced in [23], and of defining and analysing the new concept of asymptotic exponential cone of a family of Metzler matrices (along a certain direction). These results will provide necessary and/or sufficient conditions for the solvability of an interesting algebraic problem that arises in the context of continuous-time positive switched systems and, specifically, in the investigation of the reachability property [21,22,25].     

Embedding cycles of various lengths into star graphs with both edge and vertex faults

The n-dimensional star graph S_n is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let F_v and F_e be the sets of faulty vertices and faulty edges of S_n, respectively. We prove that S_n − F_v − F_e contains a fault-free cycle of every even length from 6 to n! − 2∣F_v∣ with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4. We also show that S_n − F_v − F_e contains a fault-free path of length n! − 2∣F_v∣ − 1 (respectively, n! − 2∣F_v∣ − 2) between two arbitrary vertices of S_n in different partite sets (respectively, the same partite set) with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4.     

Spectrum of a homogeneous graph

We describe the spectrum of the Laplacian for a homogeneous graph acted on by a discrete group. This follows from a more general result which describes the spectrum of a convolution operator on a homogeneous space of a locally compact group. We also prove a version of Harnack inequality for a Schrödinger operator on an invariant homogeneous graph.     

Cayley color graphs of inverse semigroups and groupoids

The notion of Cayley color graphs of groups is generalized to inverse semigroups and groupoids. The set of partial automorphisms of the Cayley color graph of an inverse semigroup or a groupoid is isomorphic to the original inverse semigroup or groupoid. The groupoid of color permuting partial automorphisms of the Cayley color graph of a transitive groupoid is isomorphic to the original groupoid.     

Cayley graphs of the group ℤ4 and limits for minimal vertex-primitive graphs of HA-type

We point out a countable set of pairwise nonisomorphic Cayley graphs of the group ℤ⁴ that are limit for finite minimal vertex-primitive graphs admitting a vertex-primitive automorphism group containing a regular Abelian normal subgroup. Supported by RFBR grant No. 06-01-00378. __________ Translated from Algebra i Logika, Vol. 47, No. 2, pp. 203–214, March–April, 2008.     

Quasi‐random graphs with given degree sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z _n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008