6 papers · 1 filter
Relating the independence number and the dissociation number
Felix Bock, Johannes Pardey, Lucia D. Penso +1
The independence number and the dissociation number of a graph are the largest orders of induced subgraphs of of maximum degree at most and at mo…
A bound on the dissociation number
Felix Bock, Johannes Pardey, Lucia D. Penso +1
The dissociation number of a graph is the maximum order of a set of vertices of inducing a subgraph that is of maximum degree at most . Computing the dis…
Relating dissociation, independence, and matchings
Felix Bock, Johannes Pardey, Lucia D. Penso +1
A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most . Computing the dissociation number of a given graph , define…
Partial immunization of trees
Mitre C. Dourado, Stefan Ehard, Lucia D. Penso +1
For a graph and an integer-valued function on its vertex set, a dynamic monopoly is a set of vertices of such that iteratively adding to it vertices of that hav…
Identifying Codes in the Complementary Prism of Cycles
Marcia R. Cappelle, Erika M. M. Coelho, Hebert Coelho +2
We show that an identifying code of minimum order in the complementary prism of a cycle of order has order . Furthermore, we observe that the clique-width of the com…
Graphs in which some and every maximum matching is uniquely restricted
Lucia Draque Penso, Dieter Rautenbach, Ueverton dos Santos Souza
A matching in a graph is uniquely restricted if there is no matching in that is distinct from but covers the same vertices as . Solving a problem posed by G…