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
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.
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.
We show that an identifying code of minimum order in the complementary prism of a cycle of order n has order 7n/9+Θ(1). Furthermore, we observe that the clique-width of the complementary prism of a graph of clique-width k is at most 4k, and discuss some algorithmic consequences.
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.