For a vertex in a graph , the set consists of those vertices of whose distance from is 2. If a graph contains a set of vertices such that the sets , , form a partition of , then is called a -step domination graph. We describe -step domination graphs possessing some prescribed property. In addition, all -step domination paths and cycles are determined.
In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive...
We formulate and prove a formula to compute the expected value of the minimal random basis of an arbitrary finite matroid whose elements are assigned weights which are independent and uniformly distributed on the interval [0, 1]. This method yields an exact formula in terms of the Tutte polynomial. We give a simple formula to find the minimal random basis of the projective geometry PG(r − 1, q).
In this paper, we recall the existence of graphs with bounded valency such that the simple random walk has a return probability at time at the origin of order for fixed and with Følner function . This result was proved by Erschler (see [4], [3]); we give a more detailed proof of this construction in the appendix. In the second part, we give an application of the existence of such graphs. We obtain bounds of the correct order for some functional of the local time of a simple random walk on...
We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).
We prove that the Cayley graphs of are expanders with respect to the projection of any fixed elements in generating a Zariski dense subgroup.
We show that random Cayley graphs of finite simple (or semisimple) groups of Lie type of fixed rank are expanders. The proofs are based on the Bourgain-Gamburd method and on the main result of our companion paper [BGGT].
Let be a fixed symmetric finite subset of that generates a Zariski dense subgroup of when we consider it as an algebraic group over by restriction of scalars. We prove that the Cayley graphs of with respect to the projections of is an expander family if ranges over square-free ideals of if and is an arbitrary numberfield, or if and .