BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let G be a finite, simple, and undirected graph of order n and average degree d. Up to terms of smaller order, we characterize the minimal intervals I containing d that are guaranteed to contain some vertex degree. In particular, for d+∈(dn,n−1], we show the existence of a vertex in G of degree between d+−(n−d++d+2−dn(d+−d)n) and d+.
The dissociation number diss(G) of a graph G is the maximum order of a set of vertices of G inducing a subgraph that is of maximum degree at most 1. Computing the dissociation number of a given graph is algorithmically hard even when restricted to subcubic bipartite graphs. For a graph G with n vertices, m edges, k components, and c1 induced cycles of length 1 modulo 3, we show diss(G)≥n−31(m+k+c1). Furthermore, we characterize the extremal graphs in which every two cycles are vertex-disjoint.
We propose the notion of a majority k-edge-coloring of a graph G, which is an edge-coloring of G with k colors such that, for every vertex u of G, at most half the edges of G incident with u have the same color. We show the best possible results that every graph of minimum degree at least 2 has a majority 4-edge-coloring, and that every graph of minimum degree at least 4 has a majority 3-edge-coloring. Furthermore, we discuss a natural variation of majority edge-colorings and some related open problems.
A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most 1. Computing the dissociation number diss(G) of a given graph G, defined as the order of a maximum dissociation set in G, is algorithmically hard even when G is restricted to be bipartite. Recently, Hosseinian and Butenko proposed a simple 34-approximation algorithm for the dissociation number problem in bipartite graphs. Their result relies on the inequality diss(G)≤34α(G−M) implicit in their work, where G is a bipartite graph, M is a maximum matching in G, and α(G−M) denotes the independence number of G−M. We show that the pairs (G,M) for which this inequality holds with equality can be recognized efficiently, and that a maximum dissociation set can be determined for them efficiently. The dissociation number of a graph G satisfies max{α(G),2νs(G)}≤diss(G)≤α(G)+νs(G)≤2α(G), where νs(G) denotes the induced matching number of G. We show that deciding whether diss(G) equals any of the four terms lower and upper bounding diss(G) is NP-hard.
The independence number α(G) and the dissociation number diss(G) of a graph G are the largest orders of induced subgraphs of G of maximum degree at most 0 and at most 1, respectively. We consider possible improvements of the obvious inequality 2α(G)≥diss(G). For connected cubic graphs G distinct from K4, we show 5α(G)≥3diss(G), and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle-free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs.
For a fixed positive ε, we show the existence of a constant Cε with the following property: Given a ±1-edge-labeling c:E(Kn)→{−1,1} of the complete graph Kn with c(E(Kn))=0, and a spanning forest F of Kn of maximum degree Δ, one can determine in polynomial time an isomorphic copy F′ of F in Kn with ∣c(E(F′))∣≤(43+ε)Δ+Cε. Our approach is based on the method of conditional expectation.
For a complete graph Kn of order n, an edge-labeling c:E(Kn)→{−1,1} satisfying c(E(Kn))=0, and a spanning forest F of Kn, we consider the problem to minimize ∣c(E(F′))∣ over all isomorphic copies F′ of F in Kn. In particular, we ask under which additional conditions there is a zero-sum copy, that is, a copy F′ of F with c(E(F′))=0. We show that there is always a copy F′ of F with ∣c(E(F′))∣≤Δ(F)+1, where Δ(F) is the maximum degree of F. We conjecture that this bound can be improved to ∣c(E(F′))∣≤(Δ(F)−1)/2 and verify this for F being the star K1,n−1. Under some simple necessary divisibility conditions, we show the existence of a zero-sum P3-factor, and, for sufficiently large n, also of a zero-sum P4-factor.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.