Displaying similar documents to “Regularity of powers of binomial edge ideals of complete multipartite graphs”

On the regularity and defect sequence of monomial and binomial ideals

Keivan Borna, Abolfazl Mohajer (2019)

Czechoslovak Mathematical Journal

Similarity:

When S is a polynomial ring or more generally a standard graded algebra over a field K , with homogeneous maximal ideal 𝔪 , it is known that for an ideal I of S , the regularity of powers of I becomes eventually a linear function, i.e., reg ( I m ) = d m + e for m 0 and some integers d , e . This motivates writing reg ( I m ) = d m + e m for every m 0 . The sequence e m , called the of the ideal I , is the subject of much research and its nature is still widely unexplored. We know that e m is eventually constant. In this article, after proving...

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 .

The operation and * operation of Cohen-Macaulay bipartite graphs

Yulong Yang, Guangjun Zhu, Yijun Cui, Shiya Duan (2024)

Czechoslovak Mathematical Journal

Similarity:

Let G be a finite simple graph with the vertex set V and let I G be its edge ideal in the polynomial ring S = 𝕂 [ V ] . We compute the depth and the Castelnuovo-Mumford regularity of S / I G when G = G 1 G 2 or G = G 1 * G 2 is a graph obtained from Cohen-Macaulay bipartite graphs G 1 , G 2 by the operation or * operation, respectively.

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

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

A note on the multiplier ideals of monomial ideals

Cheng Gong, Zhongming Tang (2015)

Czechoslovak Mathematical Journal

Similarity:

Let 𝔞 [ x 1 , ... , x n ] be a monomial ideal and 𝒥 ( 𝔞 c ) the multiplier ideal of 𝔞 with coefficient c . Then 𝒥 ( 𝔞 c ) is also a monomial ideal of [ x 1 , ... , x n ] , and the equality 𝒥 ( 𝔞 c ) = 𝔞 implies that 0 < c < n + 1 . We mainly discuss the problem when 𝒥 ( 𝔞 ) = 𝔞 or 𝒥 ( 𝔞 n + 1 - ε ) = 𝔞 for all 0 < ε < 1 . It is proved that if 𝒥 ( 𝔞 ) = 𝔞 then 𝔞 is principal, and if 𝒥 ( 𝔞 n + 1 - ε ) = 𝔞 holds for all 0 < ε < 1 then 𝔞 = ( x 1 , ... , x n ) . One global result is also obtained. Let 𝔞 ˜ be the ideal sheaf on n - 1 associated with 𝔞 . Then it is proved that the equality 𝒥 ( 𝔞 ˜ ) = 𝔞 ˜ implies that 𝔞 ˜ is principal.

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

Degree sums of adjacent vertices for traceability of claw-free graphs

Tao Tian, Liming Xiong, Zhi-Hong Chen, Shipeng Wang (2022)

Czechoslovak Mathematical Journal

Similarity:

The line graph of a graph G , denoted by L ( G ) , has E ( G ) as its vertex set, where two vertices in L ( G ) are adjacent if and only if the corresponding edges in G have a vertex in common. For a graph H , define σ ¯ 2 ( H ) = min { d ( u ) + d ( v ) : u v E ( H ) } . Let H be a 2-connected claw-free simple graph of order n with δ ( H ) 3 . We show that, if σ ¯ 2 ( H ) 1 7 ( 2 n - 5 ) and n is sufficiently large, then either H is traceable or the Ryjáček’s closure cl ( H ) = L ( G ) , where G is an essentially 2 -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

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

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