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

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

Displaying similar documents to “Sum labellings of cycle hypergraphs”

The sum number of d-partite complete hypergraphs

Hanns-Martin Teichert (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph d ( S ) = ( V , ) , where V = S and = v , . . . , v d : ( i j v i v j ) i = 1 d v i S . For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices w , . . . , w σ V such that w , . . . , w σ is a sum hypergraph. In this paper, we prove σ ( n , . . . , n d d ) = 1 + i = 1 d ( n i - 1 ) + m i n 0 , 1 / 2 ( i = 1 d - 1 ( n i - 1 ) - n d ) , where n , . . . , n d d denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

Classes of hypergraphs with sum number one

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph d ̲ , d ̅ ( S ) = ( V , ) where V = S and = e S : d ̲ < | e | < d ̅ v e v S . For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices w , . . . , w σ V such that w , . . . , w σ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition...

Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás, Zsolt Tuza, Vitaly Voloshin (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = E₁,...,Eₘ, together with integers s i and t i satisfying 1 s i t i | E i | for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge E i satisfies s i | φ ( E i ) | t i . The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a “host graph”, that means a graph G on the same vertex set X as ℋ, such that each E i induces a connected subgraph in G....

Bounds for the number of meeting edges in graph partitioning

Qinghou Zeng, Jianfeng Hou (2017)

Czechoslovak Mathematical Journal

Similarity:

Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least ( w 1 - Δ 1 ) / 2 + 2 w 2 / 3 , where w i is the total weight of edges of size i and Δ 1 is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least ( w 0 - 1 ) / 6 + ( w 1 - Δ 1 ) / 3 + 2 w 2 / 3 , where...

Fires on trees

Jean Bertoin (2012)

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

Similarity:

We consider random dynamics on the edges of a uniform Cayley tree with n vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate n - α on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as n , the terminal density of fireproof...

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.

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 subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

Similarity:

We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for...

A note on a conjecture on niche hypergraphs

Pawaton Kaemawichanurat, Thiradet Jiarasuksakun (2019)

Czechoslovak Mathematical Journal

Similarity:

For a digraph D , the niche hypergraph N ( D ) of D is the hypergraph having the same set of vertices as D and the set of hyperedges E ( N ( D ) ) = { e V ( D ) : | e | 2 and there exists a vertex v such that e = N D - ( v ) or e = N D + ( v ) } . A digraph is said to be acyclic if it has no directed cycle as a subdigraph. For a given hypergraph , the niche number n ^ ( ) is the smallest integer such that together with n ^ ( ) isolated vertices is the niche hypergraph of an acyclic digraph. C. Garske, M. Sonntag and H. M. Teichert (2016) conjectured that for a linear...

Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai Sun, Min Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

A proper vertex coloring of a graph G is acyclic if there is no bicolored cycle in G . In other words, each cycle of G must be colored with at least three colors. Given a list assignment L = { L ( v ) : v V } , if there exists an acyclic coloring π of G such that π ( v ) L ( v ) for all v V , then we say that G is acyclically L -colorable. If G is acyclically L -colorable for any list assignment L with | L ( v ) | k for all v V , then G is acyclically k -choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without...

On-line ranking number for cycles and paths

Erik Bruoth, Mirko Horňák (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number χ * r ( G ) of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that χ * r ( P ) < 3 l o g n for n ≥ 2....

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

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang An, Liming Xiong, Runli Tian (2015)

Czechoslovak Mathematical Journal

Similarity:

An edge of G is singular if it does not lie on any triangle of G ; otherwise, it is non-singular. A vertex u of a graph G is called locally connected if the induced subgraph G [ N ( u ) ] by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph G of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex v of degree at least 3 in G , there is a nonnegative integer s such...