Displaying 1681 – 1700 of 5365

Showing per page

Exact 2 -step domination in graphs

Gary Chartrand, Frank Harary, Moazzem Hossain, Kelly Schultz (1995)

Mathematica Bohemica

For a vertex v in a graph G , the set N 2 ( v ) consists of those vertices of G whose distance from v is 2. If a graph G contains a set S of vertices such that the sets N 2 ( v ) , v S , form a partition of V ( G ) , then G is called a 2 -step domination graph. We describe 2 -step domination graphs possessing some prescribed property. In addition, all 2 -step domination paths and cycles are determined.

Exact double domination in graphs

Mustapha Chellali, Abdelkader Khelladi, Frédéric Maffray (2005)

Discussiones Mathematicae Graph Theory

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...

Exact Expectation and Variance of Minimal Basis of Random Matroids

Wojciech Kordecki, Anna Lyczkowska-Hanćkowiak (2013)

Discussiones Mathematicae Graph Theory

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).

Existence of graphs with sub exponential transitions probability decay and applications

Clément Rau (2010)

Bulletin de la Société Mathématique de France

In this paper, we recall the existence of graphs with bounded valency such that the simple random walk has a return probability at time n at the origin of order exp ( - n α ) , for fixed α [ 0 , 1 [ and with Følner function exp ( n 2 α 1 - α ) . 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...

Existence of perfect matchings in a plane bipartite graph

Zhongyuan Che (2010)

Czechoslovak Mathematical Journal

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).

Expansion and random walks in SL d ( / p n ) : I

Jean Bourgain, Alex Gamburd (2008)

Journal of the European Mathematical Society

We prove that the Cayley graphs of SL d ( / p n ) are expanders with respect to the projection of any fixed elements in SL d ( ) generating a Zariski dense subgroup.

Expansion in finite simple groups of Lie type

Emmanuel Breuillard, Ben J. Green, Robert Guralnick, Terence Tao (2015)

Journal of the European Mathematical Society

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].

Expansion in S L d ( 𝒪 K / I ) , I square-free

Péter P. Varjú (2012)

Journal of the European Mathematical Society

Let S be a fixed symmetric finite subset of S L d ( 𝒪 K ) that generates a Zariski dense subgroup of S L d ( 𝒪 K ) when we consider it as an algebraic group over m a t h b b Q by restriction of scalars. We prove that the Cayley graphs of S L d ( 𝒪 K / I ) with respect to the projections of S is an expander family if I ranges over square-free ideals of 𝒪 K if d = 2 and K is an arbitrary numberfield, or if d = 3 and K = .

Currently displaying 1681 – 1700 of 5365