Displaying similar documents to “On the diameter of the intersection graph of a finite simple group”

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

Edge-colouring of graphs and hereditary graph properties

Samantha Dorfling, Tomáš Vetrík (2016)

Czechoslovak Mathematical Journal

Similarity:

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph G , a hereditary graph property 𝒫 and l 1 we define χ 𝒫 , l ' ( G ) to be the minimum number of colours needed to properly colour the edges of G , such that any subgraph of G induced by edges coloured by (at most) l colours is in 𝒫 . We present a necessary and sufficient condition for the existence of χ 𝒫 , l ' ( G ) . We focus on edge-colourings of graphs with respect to the hereditary...

On the bounds of Laplacian eigenvalues of k -connected graphs

Xiaodan Chen, Yaoping Hou (2015)

Czechoslovak Mathematical Journal

Similarity:

Let μ n - 1 ( G ) be the algebraic connectivity, and let μ 1 ( G ) be the Laplacian spectral radius of a k -connected graph G with n vertices and m edges. In this paper, we prove that μ n - 1 ( G ) 2 n k 2 ( n ( n - 1 ) - 2 m ) ( n + k - 2 ) + 2 k 2 , with equality if and only if G is the complete graph K n or K n - e . Moreover, if G is non-regular, then μ 1 ( G ) < 2 Δ - 2 ( n Δ - 2 m ) k 2 2 ( n Δ - 2 m ) ( n 2 - 2 n + 2 k ) + n k 2 , where Δ stands for the maximum degree of G . Remark that in some cases, these two inequalities improve some previously known results.

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

Some properties of generalized distance eigenvalues of graphs

Yuzheng Ma, Yan Ling Shao (2024)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple connected graph with vertex set V ( G ) = { v 1 , v 2 , , v n } and edge set E ( G ) , and let d v i be the degree of the vertex v i . Let D ( G ) be the distance matrix and let T r ( G ) be the diagonal matrix of the vertex transmissions of G . The generalized distance matrix of G is defined as D α ( G ) = α T r ( G ) + ( 1 - α ) D ( G ) , where 0 α 1 . Let λ 1 ( D α ( G ) ) λ 2 ( D α ( G ) ) ... λ n ( D α ( G ) ) be the generalized distance eigenvalues of G , and let k be an integer with 1 k n . We denote by S k ( D α ( G ) ) = λ 1 ( D α ( G ) ) + λ 2 ( D α ( G ) ) + ... + λ k ( D α ( G ) ) the sum of the k largest generalized distance eigenvalues. The generalized distance spread of a graph G is defined as D α S ( G ) = λ 1 ( D α ( G ) ) - λ n ( D α ( G ) ) ....

On γ-labelings of trees

Gary Chartrand, David Erwin, Donald W. VanderJagt, Ping Zhang (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is v a l ( f ) = Σ e E ( G ) f ' K ( e ) . The maximum value of a γ-labeling of G is defined as v a l m a x ( G ) = m a x v a l ( f ) : f i s a γ - l a b e l i n g o f G ; while the minimum value of a γ-labeling of G is v a l m i n ( G ) = m i n v a l ( f ) : f i s a γ - l a b e l i n g o f G ; The values v a l m a x ( S p , q ) and v a l m i n ( S p , q ) are determined for double stars S p , q . We present characterizations of connected graphs G of order n for which...

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for g ( n , l ) , the biggest number k guaranteeing that there exist l graphs on n vertices, each two having edit distance at least k . By edit distance of two graphs G , F we mean the number of edges needed to be added to or deleted from graph G to obtain graph F . This new extremal number g ( n , l ) is closely linked to the edit distance of graphs. Using probabilistic methods we show...

A note on solvable vertex stabilizers of s -transitive graphs of prime valency

Song-Tao Guo, Hailong Hou, Yong Xu (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph X , with a group G of automorphisms of X , is said to be ( G , s ) -transitive, for some s 1 , if G is transitive on s -arcs but not on ( s + 1 ) -arcs. Let X be a connected ( G , s ) -transitive graph of prime valency p 5 , and G v the vertex stabilizer of a vertex v V ( X ) . Suppose that G v is solvable. Weiss (1974) proved that | G v | p ( p - 1 ) 2 . In this paper, we prove that G v ( p m ) × n for some positive integers m and n such that n div m and m p - 1 .

Complete pairs of coanalytic sets

Jean Saint Raymond (2007)

Fundamenta Mathematicae

Similarity:

Let X be a Polish space, and let C₀ and C₁ be disjoint coanalytic subsets of X. The pair (C₀,C₁) is said to be complete if for every pair (D₀,D₁) of disjoint coanalytic subsets of ω ω there exists a continuous function f : ω ω X such that f - 1 ( C ) = D and f - 1 ( C ) = D . We give several explicit examples of complete pairs of coanalytic sets.

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

Classification of rings with toroidal Jacobson graph

Krishnan Selvakumar, Manoharan Subajini (2016)

Czechoslovak Mathematical Journal

Similarity:

Let R be a commutative ring with nonzero identity and J ( R ) the Jacobson radical of R . The Jacobson graph of R , denoted by 𝔍 R , is defined as the graph with vertex set R J ( R ) such that two distinct vertices x and y are adjacent if and only if 1 - x y is not a unit of R . The genus of a simple graph G is the smallest nonnegative integer n such that G can be embedded into an orientable surface S n . In this paper, we investigate the genus number of the compact Riemann surface in which 𝔍 R can be embedded and...

Size of the giant component in a random geometric graph

Ghurumuruhan Ganesan (2013)

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

Similarity:

In this paper, we study the size of the giant component C G in the random geometric graph G = G ( n , r n , f ) of n nodes independently distributed each according to a certain density f ( · ) in [ 0 , 1 ] 2 satisfying inf x [ 0 , 1 ] 2 f ( x ) g t ; 0 . If c 1 n r n 2 c 2 log n n for some positive constants c 1 , c 2 and n r n 2 as n , we show that the giant component of G contains at least n - o ( n ) nodes with probability at least 1 - e - β n r n 2 for all n and for some positive constant β . We also obtain estimates on the diameter and number of the non-giant components of G .

Several quantitative characterizations of some specific groups

A. Mohammadzadeh, Ali Reza Moghaddamfar (2017)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let G be a finite group and let π ( G ) = { p 1 , p 2 , ... , p k } be the set of prime divisors of | G | for which p 1 < p 2 < < p k . The Gruenberg-Kegel graph of G , denoted GK ( G ) , is defined as follows: its vertex set is π ( G ) and two different vertices p i and p j are adjacent by an edge if and only if G contains an element of order p i p j . The degree of a vertex p i in GK ( G ) is denoted by d G ( p i ) and the k -tuple D ( G ) = ( d G ( p 1 ) , d G ( p 2 ) , ... , d G ( p k ) ) is said to be the degree pattern of G . Moreover, if ω π ( G ) is the vertex set of a connected component of GK ( G ) , then the largest ω -number which divides | G | , is...