Displaying similar documents to “Maximum bipartite subgraphs in H -free graphs”

A new characterization of symmetric group by NSE

Azam Babai, Zeinab Akhlaghi (2017)

Czechoslovak Mathematical Journal

Similarity:

Let G be a group and ω ( G ) be the set of element orders of G . Let k ω ( G ) and m k ( G ) be the number of elements of order k in G . Let nse ( G ) = { m k ( G ) : k ω ( G ) } . Assume r is a prime number and let G be a group such that nse ( G ) = nse ( S r ) , where S r is the symmetric group of degree r . In this paper we prove that G S r , if r divides the order of G and r 2 does not divide it. To get the conclusion we make use of some well-known results on the prime graphs of finite simple groups and their components.

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

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

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 g c -colorings of nearly bipartite graphs

Yuzhuo Zhang, Xia Zhang (2018)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple graph, let d ( v ) denote the degree of a vertex v and let g be a nonnegative integer function on V ( G ) with 0 g ( v ) d ( v ) for each vertex v V ( G ) . A g c -coloring of G is an edge coloring such that for each vertex v V ( G ) and each color c , there are at least g ( v ) edges colored c incident with v . The g c -chromatic index of G , denoted by χ g c ' ( G ) , is the maximum number of colors such that a g c -coloring of G exists. Any simple graph G has the g c -chromatic index equal to δ g ( G ) or δ g ( G ) - 1 , where δ g ( G ) = min v V ( G ) d ( v ) / g ( v ) . A graph G is nearly bipartite,...

On path-quasar Ramsey numbers

Binlong Li, Bo Ning (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let G 1 and G 2 be two given graphs. The Ramsey number R ( G 1 , G 2 ) is the least integer r such that for every graph G on r vertices, either G contains a G 1 or G ¯ contains a G 2 . Parsons gave a recursive formula to determine the values of R ( P n , K 1 , m ) , where P n is a path on n vertices and K 1 , m is a star on m + 1 vertices. In this note, we study the Ramsey numbers R ( P n , K 1 F m ) , where F m is a linear forest on m vertices. We determine the exact values of R ( P n , K 1 F m ) for the cases m n and m 2 n , and for the case that F m has no odd component. Moreover, we...

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 Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths

Halina Bielak, Kinga Dąbrowska (2015)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

The Ramsey number R ( G , H ) for a pair of graphs G and H is defined as the smallest integer n such that, for any graph F on n vertices, either F contains G or F ¯ contains H as a subgraph, where F ¯ denotes the complement of F . We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers R ( K 1 + L n , P m ) and R ( K 1 + L n , C m ) for some integers m , n , where L n is...

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

Note on improper coloring of 1 -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph G = ( V , E ) is called improperly ( d 1 , , d k ) -colorable if the vertex set V can be partitioned into subsets V 1 , , V k such that the graph G [ V i ] induced by the vertices of V i has maximum degree at most d i for all 1 i k . In this paper, we mainly study the improper coloring of 1 -planar graphs and show that 1 -planar graphs with girth at least 7 are ( 2 , 0 , 0 , 0 ) -colorable.

On the recognizability of some projective general linear groups by the prime graph

Masoumeh Sajjadi (2022)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let G be a finite group. The prime graph of G is a simple graph Γ ( G ) whose vertex set is π ( G ) and two distinct vertices p and q are joined by an edge if and only if G has an element of order p q . A group G is called k -recognizable by prime graph if there exist exactly k nonisomorphic groups H satisfying the condition Γ ( G ) = Γ ( H ) . A 1-recognizable group is usually called a recognizable group. In this problem, it was proved that PGL ( 2 , p α ) is recognizable, if p is an odd prime and α > 1 is odd. But for even α , only...

The real symmetric matrices of odd order with a P-set of maximum size

Zhibin Du, Carlos Martins da Fonseca (2016)

Czechoslovak Mathematical Journal

Similarity:

Suppose that A is a real symmetric matrix of order n . Denote by m A ( 0 ) the nullity of A . For a nonempty subset α of { 1 , 2 , ... , n } , let A ( α ) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α . When m A ( α ) ( 0 ) = m A ( 0 ) + | α | , we call α a P-set of A . It is known that every P-set of A contains at most n / 2 elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As...