Displaying similar documents to “Size of the giant component in a random geometric graph”

Uniform mixing time for random walk on lamplighter graphs

Júlia Komjáthy, Jason Miller, Yuval Peres (2014)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Suppose that 𝒢 is a finite, connected graph and X is a lazy random walk on 𝒢 . The lamplighter chain X associated with X is the random walk on the wreath product 𝒢 = 𝐙 2 𝒢 , the graph whose vertices consist of pairs ( f ̲ , x ) where f is a labeling of the vertices of 𝒢 by elements of 𝐙 2 = { 0 , 1 } and x is a vertex in 𝒢 . There is an edge between ( f ̲ , x ) and ( g ̲ , y ) in 𝒢 if and only if x is adjacent to y in 𝒢 and f z = g z for all z x , y . In each step, X moves from a configuration ( f ̲ , x ) by updating x to y using the transition rule of X and then...

Saturation numbers for linear forests P 6 + t P 2

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph G is H -saturated if it contains no H as a subgraph, but does contain H after the addition of any edge in the complement of G . The saturation number, sat ( n , H ) , is the minimum number of edges of a graph in the set of all H -saturated graphs of order n . We determine the saturation number sat ( n , P 6 + t P 2 ) for n 10 3 t + 10 and characterize the extremal graphs for n > 10 3 t + 20 .

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

Similarity:

The generalized k -connectivity κ k ( G ) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k -edge-connectivity which is defined as λ k ( G ) = min { λ ( S ) : S V ( G ) and | S | = k } , where λ ( S ) denotes the maximum number of pairwise edge-disjoint trees T 1 , T 2 , ... , T in G such that S V ( T i ) for 1 i . In this paper we prove that for any two connected graphs G and H we have λ 3 ( G H ) λ 3 ( G ) + λ 3 ( H ) , where G H is the Cartesian product of G and H . Moreover, the bound is sharp. We also...

The small Ree group 2 G 2 ( 3 2 n + 1 ) and related graph

Alireza K. Asboei, Seyed S. S. Amiri (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let G be a finite group. The main supergraph 𝒮 ( G ) is a graph with vertex set G in which two vertices x and y are adjacent if and only if o ( x ) o ( y ) or o ( y ) o ( x ) . In this paper, we will show that G 2 G 2 ( 3 2 n + 1 ) if and only if 𝒮 ( G ) 𝒮 ( 2 G 2 ( 3 2 n + 1 ) ) . As a main consequence of our result we conclude that Thompson’s problem is true for the small Ree group 2 G 2 ( 3 2 n + 1 ) .

Even factor of bridgeless graphs containing two specified edges

Nastaran Haghparast, Dariush Kiani (2018)

Czechoslovak Mathematical Journal

Similarity:

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let G be a bridgeless simple graph with minimum degree at least 3 . Jackson and Yoshimoto (2007) showed that G has an even factor containing two arbitrary prescribed edges. They also proved that G has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges e 1 and e 2 of G , there is an even factor containing e 1 and e 2 ...

Sum-product theorems and incidence geometry

Mei-Chu Chang, Jozsef Solymosi (2007)

Journal of the European Mathematical Society

Similarity:

In this paper we prove the following theorems in incidence geometry. 1. There is δ > 0 such that for any P 1 , , P 4 , and Q 1 , , Q n 2 , if there are n ( 1 + δ ) / 2 many distinct lines between P i and Q j for all i , j , then P 1 , , P 4 are collinear. If the number of the distinct lines is < c n 1 / 2 then the cross ratio of the four points is algebraic. 2. Given c > 0 , there is δ > 0 such that for any P 1 , P 2 , P 3 2 noncollinear, and Q 1 , , Q n 2 , if there are c n 1 / 2 many distinct lines between P i and Q j for all i , j , then for any P 2 { P 1 , P 2 , P 3 } , we have δ n distinct lines between P and Q j . 3. Given...

Horocyclic products of trees

Laurent Bartholdi, Markus Neuhauser, Wolfgang Woess (2008)

Journal of the European Mathematical Society

Similarity:

Let T 1 , , T d be homogeneous trees with degrees q 1 + 1 , , q d + 1 3 , respectively. For each tree, let 𝔥 : T j be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of T 1 , , T d is the graph 𝖣𝖫 ( q 1 , , q d ) consisting of all d -tuples x 1 x d T 1 × × T d with 𝔥 ( x 1 ) + + 𝔥 ( x d ) = 0 , equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If d = 2 and q 1 = q 2 = q then we obtain a Cayley graph...

The Turán number of the graph 3 P 4

Halina Bielak, Sebastian Kieliszek (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let e x ( n , G ) denote the maximum number of edges in a graph on n vertices which does not contain G as a subgraph. Let P i denote a path consisting of i vertices and let m P i denote m disjoint copies of P i . In this paper we count e x ( n , 3 P 4 ) .

Matchings in complete bipartite graphs and the r -Lah numbers

Gábor Nyul, Gabriella Rácz (2021)

Czechoslovak Mathematical Journal

Similarity:

We give a graph theoretic interpretation of r -Lah numbers, namely, we show that the r -Lah number n k r counting the number of r -partitions of an ( n + r ) -element set into k + r ordered blocks is just equal to the number of matchings consisting of n - k edges in the complete bipartite graph with partite sets of cardinality n and n + 2 r - 1 ( 0 k n , r 1 ). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for r -Stirling numbers of the second kind. ...

The potential-Ramsey number of K n and K t - k

Jin-Zhi Du, Jian Hua Yin (2022)

Czechoslovak Mathematical Journal

Similarity:

A nonincreasing sequence π = ( d 1 , ... , d n ) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices. In this case, G is referred to as a realization of π . Given two graphs G 1 and G 2 , A. Busch et al. (2014) introduced the potential-Ramsey number of G 1 and G 2 , denoted by r pot ( G 1 , G 2 ) , as the smallest nonnegative integer m such that for every m -term graphic sequence π , there is a realization G of π with G 1 G or with G 2 G ¯ , where G ¯ is the complement of G . For t 2 and 0 k t 2 , let K t - k be the graph...