The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Bounds for the number of meeting edges in graph partitioning”

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

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

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

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

Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles

Donghan Zhang (2022)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V ( G ) , E ( G ) ) be a simple graph and E G ( v ) denote the set of edges incident with a vertex v . A neighbor sum distinguishing (NSD) total coloring φ of G is a proper total coloring of G such that z E G ( u ) { u } φ ( z ) z E G ( v ) { v } φ ( z ) for each edge u v E ( G ) . Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree Δ admits an NSD total ( Δ + 3 ) -coloring. We prove that the list version of this conjecture holds for any IC-planar graph with Δ 11 but without 5 -cycles by applying the Combinatorial Nullstellensatz.

Characterizing finite groups whose enhanced power graphs have universal vertices

David G. Costanzo, Mark L. Lewis, Stefano Schmidt, Eyob Tsegaye, Gabe Udell (2024)

Czechoslovak Mathematical Journal

Similarity:

Let G be a finite group and construct a graph Δ ( G ) by taking G { 1 } as the vertex set of Δ ( G ) and by drawing an edge between two vertices x and y if x , y is cyclic. Let K ( G ) be the set consisting of the universal vertices of Δ ( G ) along the identity element. For a solvable group G , we present a necessary and sufficient condition for K ( G ) to be nontrivial. We also develop a connection between Δ ( G ) and K ( G ) when | G | is divisible by two distinct primes and the diameter of Δ ( G ) is 2.

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

Distance matrices perturbed by Laplacians

Balaji Ramamurthy, Ravindra Bhalchandra Bapat, Shivani Goel (2020)

Applications of Mathematics

Similarity:

Let T be a tree with n vertices. To each edge of T we assign a weight which is a positive definite matrix of some fixed order, say, s . Let D i j denote the sum of all the weights lying in the path connecting the vertices i and j of T . We now say that D i j is the distance between i and j . Define D : = [ D i j ] , where D i i is the s × s null matrix and for i j , D i j is the distance between i and j . Let G be an arbitrary connected weighted graph with n vertices, where each weight is a positive definite matrix of order...

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

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

Partitioning planar graph of girth 5 into two forests with maximum degree 4

Min Chen, André Raspaud, Weifan Wang, Weiqiang Yu (2024)

Czechoslovak Mathematical Journal

Similarity:

Given a graph G = ( V , E ) , if we can partition the vertex set V into two nonempty subsets V 1 and V 2 which satisfy Δ ( G [ V 1 ] ) d 1 and Δ ( G [ V 2 ] ) d 2 , then we say G has a ( Δ d 1 , Δ d 2 ) -partition. And we say G admits an ( F d 1 , F d 2 ) -partition if G [ V 1 ] and G [ V 2 ] are both forests whose maximum degree is at most d 1 and d 2 , respectively. We show that every planar graph with girth at least 5 has an ( F 4 , F 4 ) -partition.