Search results for: Yair Caro

Items from 1 to 20 out of 40 results

article

Counting connected partitions of graphs

Yair Caro, Balázs Patkós, Zsolt Tuza, Máté Vizer

Journal of Graph Theory > 107 > 2 > 381 - 392

Motivated by the theorem of Győri and Lovász, we consider the following problem. For a connected graph

G

n

vertices and

m

edges determine the number

P (G, k)

of unordered solutions of positive integers

\sum_{i = 1}^{k} m_{i} = m

such that every

m_{i}

is realized by a connected subgraph

H_{i}

G

with

m_{i}

edges. We also consider the vertex‐partition...

article

Unavoidable chromatic patterns in 2‐colorings of the complete graph

Yair Caro, Adriana Hansberg, Amanda Montejano

Journal of Graph Theory > 97 > 1 > 123 - 147

Given a graph

G

k

edges, we consider the following two extremal problems: provided

n

is large enough, what is the minimum integer

bal (n, G)

, if it exists, such that any 2‐coloring of the edges of a complete graph on

n

vertices having more than

bal (n, G)

edges in each color class, contains a balanced copy of

G

, that is, a copy of

G

with exactly

⌊ k ∕ 2 ⌋

edges in one of the colors? Graphs for which this...

article

Zero-Sum $$K_m$$ K m Over $${{{\mathbb {Z}}}}$$ Z and the Story of $$K_4$$ K 4

Yair Caro, Adriana Hansberg, Amanda Montejano

Graphs and Combinatorics > 2019 > 35 > 4 > 855-865

We prove the following results solving a problem raised by Caro and Yuster (Graphs Comb 32:49–63, 2016). For a positive integer $$m\ge 2$$ m ≥ 2 , $$m\ne 4$$ m ≠ 4 , there are infinitely many values of n such that the following holds: There is a weighting function $$f:E(K_n)\rightarrow \{-1,1\}$$ f : E ( K n ) → { - 1 , 1 } (and hence a weighting function $$f: E(K_n)\rightarrow...

article

The Effect of Local Majority on Global Majorityin Connected Graphs

Yair Caro, Raphael Yuster

Graphs and Combinatorics > 2018 > 34 > 6 > 1469-1487

Let $$\mathcal G$$ G be an infinite family of connected graphs and let k be a positive integer. We say that k is forcing for $$\mathcal G$$ G if for all $$G \in \mathcal G$$ G∈G but finitely many, the following holds. Any $$\{-1,1\}$$ {-1,1} -weighing of the edges of G for which all connected subgraphs on k edges are positively weighted implies that G is positively weighted. Otherwise, we say that...

article

Ramsey numbers for degree monotone paths

Yair Caro, Raphael Yuster, Christina Zarb

Discrete Mathematics > 2017 > 340 > 2 > 124-131

A path v 1 , v 2 , … , v m in a graph G is degree-monotone if d e g ( v 1 ) ≤ d e g ( v 2 ) ≤ ⋯ ≤ d e g ( v m ) where d e g ( v i ) is the degree of v i in G . Longest degree-monotone paths have been studied in several recent papers. Here we consider the Ramsey type problem for degree monotone paths. Denote by M k ( m ) ...

article

Regular independent sets

Yair Caro, Adriana Hansberg, Ryan Pepper

Discrete Applied Mathematics > 2016 > 203 > C > 35-46

The regular independence number, introduced by Albertson and Boutin in 1990, is the size of a largest set of independent vertices with the same degree. Lower bounds were proven for this invariant, in terms of the order, for trees and planar graphs. In this article, we generalize and extend these results to find lower bounds for the regular k-independence number for trees, forests, planar graphs, k-trees...

article

Selective hypergraph colourings

Yair Caro, Josef Lauri, Christina Zarb

Discrete Mathematics > 2016 > 339 > 4 > 1232-1241

We look at colourings of r-uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge E in an r-uniform hypergraph H whose vertices are coloured is the partition of r induced by the colour classes of the vertices in E. Let Q be a set of partitions of r. A Q-colouring of H is a colouring of its vertices such that only patterns appearing...

article

On Zero-Sum and Almost Zero-Sum Subgraphs Over $${\mathbb {Z}}$$ Z

Yair Caro, Raphael Yuster

Graphs and Combinatorics > 2016 > 32 > 1 > 49-63

For a graph $$H$$ H with at most $$n$$ n vertices and a weighing of the edges of $$K_n$$ K n with integers, we seek a copy of $$H$$ H in $$K_n$$ K n whose weight is minimal, possibly even zero. Of a particular interest are the cases where $$H$$ H is a spanning subgraph (or an almost spanning subgraph) and the case where $$H$$ H is...

article

Isolation in graphs

Adriana Hansberg, Yair Caro

Electronic Notes in Discrete Mathematics > 2015 > 50 > C > 465-470

Let G be a graph and F a family of graphs. We say a subset S of the vertices of G to be F-isolating if the graph induced by the vertices outside S that have no neighbors in S contains no member of F as a subgraph. The F-isolation number ι(G,F) of a graph G is the minimum cardinality among all its F-isolating sets. In this paper, we discuss several properties of the F-isolation number and then center...

article

The Saturation Number for the Length of Degree Monotone Paths

Yair Caro, Josef Lauri, Christina Zarb

Discussiones Mathematicae Graph Theory > 2015 > 35 > 3 > 557-569

A degree monotone path in a graph G is a path P such that the sequence of degrees of the vertices in the order in which they appear on P is monotonic. The length (number of vertices) of the longest degree monotone path in G is denoted by mp(G). This parameter, inspired by the well-known Erdős- Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem...

article

(2,2)-colourings and clique-free σ-hypergraphs

Yair Caro, Josef Lauri, Christina Zarb

Discrete Applied Mathematics > 2015 > 185 > Complete > 38-43

We consider vertex colourings of r-uniform hypergraphs H in the classical sense, that is such that no edge has all its vertices given the same colour, and (2,2)-colourings of H in which the vertices in any edge are given exactly two colours. This is a special case of constrained colourings introduced by Bujtas and Tuza which, in turn, is a generalization of Voloshin’s colourings of mixed hypergraphs...

article

Constrained Colouring and σ-Hypergraphs

Yair Caro, Josef Lauri, Christina Zarb

Discussiones Mathematicae Graph Theory > 2015 > 35 > 1 > 171-189

A constrained colouring or, more specifically, an (α, β)-colouring of a hypergraph H, is an assignment of colours to its vertices such that no edge of H contains less than α or more than β vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for r-uniform hypergraphs,...

article

Non-monochromatic non-rainbow colourings of σ-hypergraphs

Yair Caro, Josef Lauri

Discrete Mathematics > 2014 > 318 > Complete > 96-104

One of the most interesting new developments in hypergraph colourings in the last few years has been Voloshin’s notion of colourings of mixed hypergraphs. In this paper we shall study a specific instance of Voloshin’s idea: a non-monochromatic non-rainbow (NMNR) colouring of a hypergraph is a colouring of its vertices such that every edge has at least two vertices coloured with different colours (non-monochromatic)...

article

Simultaneous Domination in Graphs

Yair Caro, Michael A. Henning

Graphs and Combinatorics > 2014 > 30 > 6 > 1399-1416

Let $${F_1, F_2, \ldots, F_k}$$ F 1 , F 2 , … , F k be graphs with the same vertex set V. A subset $${S \subseteq V}$$ S ⊆ V is a simultaneous dominating set if for every i, 1 ≤ i ≤ k, every vertex of F _i not in S is adjacent to a vertex in S in F _i; that is, the set S is simultaneously a dominating set in each graph F _i. The cardinality of a smallest such set is...

article

Partitions of graphs into small and large sets

Asen Bojilov, Yair Caro, Adriana Hansberg, Nedyalko Nenov

Discrete Applied Mathematics > 2013 > 161 > 13-14 > 1912-1924

Let G be a graph on n vertices. We call a subset A of the vertex set V(G)k-small if, for every vertex v∈A, deg(v)≤n−|A|+k. A subset B⊆V(G) is called k-large if, for every vertex u∈B, deg(u)≥|B|−k−1. Moreover, we denote by φk(G) the minimum integer t such that there is a partition of V(G) into tk-small sets, and by Ωk(G) the minimum integer t such that there is a partition of V(G) into tk-large sets...

article

Fair domination in graphs

Yair Caro, Adriana Hansberg, Michael Henning

Discrete Mathematics > 2012 > 312 > 19 > 2905-2914

A fair dominating set in a graph G (or FD-set) is a dominating set S such that all vertices not in S are dominated by the same number of vertices from S; that is, every two vertices not in S has the same number of neighbors in S. The fair domination number, fd(G), of G is the minimum cardinality of an FD-set. Among other results, we show that if G is a connected graph of order n≥3 with no isolated...

article

Directed domination in oriented graphs

Yair Caro, Michael A. Henning

Discrete Applied Mathematics > 2012 > 160 > 7-8 > 1053-1063

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)∖S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted by Γd(G), is the maximum directed domination number γ(D) over all orientations...

article

Colorful monochromatic connectivity

Yair Caro, Raphael Yuster

Discrete Mathematics > 2011 > 311 > 16 > 1786-1792

An edge-coloring of a connected graph is monochromatically-connecting if there is a monochromatic path joining any two vertices. How “colorful” can a monochromatically-connecting coloring be? Let mc(G) denote the maximum number of colors used in a monochromatically-connecting coloring of a graph G. We prove some nontrivial upper and lower bounds for mc(G) and relate it to other graph parameters such...

article

A Greedy Partition Lemma for directed domination

Yair Caro, Michael A. Henning

Discrete Optimization > 2011 > 8 > 3 > 452-458

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)∖S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γd(G), is the maximum directed domination number γ(D) over all orientations...

article

Reconstructing graphs from size and degree properties of their induced k-subgraphs

Yair Caro, Dieter Rautenbach

Discrete Mathematics > 2007 > 307 > 6 > 694-703

As a variant of the famous graph reconstruction problem we characterize classes of graphs of order n such that all their induced subgraphs on k⩽n vertices satisfy some property related to the number of edges or to the vertex degrees.We give complete solutions for the properties (i) to be regular, (ii) to be regular modulo m⩾2 or (iii) to have one of two possible numbers of edges. Furthermore, for...

Publication date

Last year (1)
Last 3 years (1)

Close

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

From:

To:
Set your own date range

Keywords

Data set

Elsevier (28)
DML (5)
Springer (5)
Wiley (2)

Journal

Discrete Mathematics (11)
Discussiones Mathematicae Graph Theory (5)
Graphs and Combinatorics (5)
Journal of Combinatorial Theory, Series A (5)
Discrete Applied Mathematics (4)
Journal of Combinatorial Theory, Series B (3)
Journal of Graph Theory (2)
Discrete Optimization (1)
Electronic Notes in Discrete Mathematics (1)
European Journal of Combinatorics (1)
Journal of Algorithms (1)
Journal of Complexity (1)
more

INFONA - science communication portal

Search results for: Yair Caro

Counting connected partitions of graphs

Unavoidable chromatic patterns in 2‐colorings of the complete graph

Zero-Sum $$K_m$$ K m Over $${{{\mathbb {Z}}}}$$ Z and the Story of $$K_4$$ K 4

The Effect of Local Majority on Global Majorityin Connected Graphs

Ramsey numbers for degree monotone paths

Regular independent sets

Selective hypergraph colourings

On Zero-Sum and Almost Zero-Sum Subgraphs Over $${\mathbb {Z}}$$ Z

Isolation in graphs

The Saturation Number for the Length of Degree Monotone Paths

(2,2)-colourings and clique-free σ-hypergraphs

Constrained Colouring and σ-Hypergraphs

Non-monochromatic non-rainbow colourings of σ-hypergraphs

Simultaneous Domination in Graphs

Partitions of graphs into small and large sets

Fair domination in graphs

Directed domination in oriented graphs

Colorful monochromatic connectivity

A Greedy Partition Lemma for directed domination

Reconstructing graphs from size and degree properties of their induced k-subgraphs

Filter options

Publication date

Keywords

Data set

Journal

INFONA - science communication portal

Search results for: Yair Caro

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Data set

Journal

Reporting an error / abuse

Sending the report failed

Accessibility options