Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

DOI10.1016/J.DAM.2013.04.012zbMATH Open1285.05131arXiv1205.2856OpenAlexW2065166897MaRDI QIDQ2444564FDOQ2444564

Authors: Manouchehr Zaker 

Publication date: 10 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A graph $G$ is said to be a $k$-degenerate graph if any subgraph of $G$ contains a vertex of degree at most $k$. Let $kappa$ be any non-negative function on the vertex set of $G$. We first define a $kappa$-degenerate graph. Next we give an efficient algorithm to determine whether a graph is $kappa$-degenerate. We revisit the concept of dynamic monopolies in graphs. The latter notion is used in formulation and analysis of spread of influence such as disease or opinion in social networks. We consider dynamic monopolies with (not necessarily positive) but integral threshold assignments. We obtain a sufficient and necessary relationship between dynamic monopolies and generalized degeneracy. As applications of the previous results we consider the problem of determining the maximum size of $kappa$-degenerate (or $k$-degenerate) induced subgraphs in any graph. We obtain some upper and lower bounds for the maximum size of any $kappa$-degenerate induced subgraph in general and regular graphs. All of our bounds are constructive.

Full work available at URL: https://arxiv.org/abs/1205.2856

Recommendations

• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Remarks on dynamic monopolies with given average thresholds
• On dynamic monopolies of graphs with general thresholds
• On dynamic monopolies of graphs with probabilistic thresholds

zbMATH Keywords

degeneracyspread of influenceirreversible dynamic monopolyirreversible \(k\)-threshold process

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex degrees (05C07)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Large induced degenerate subgraphs
• On time versus size for monotone dynamic monopolies in regular topologies
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• On the approximability of influence in social networks
• On dynamic monopolies of graphs with general thresholds
• Combinatorial model and bounds for target set selection
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Title not available (Why is that?)
• Node-and edge-deletion NP-complete problems
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Induced Forests in Regular Graphs with Large Girth
• Title not available (Why is that?)
• Bootstrap percolation on the hypercube
• Irreversible \(k\)-threshold and majority conversion processes on complete multipartite graphs and graph products
• Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids
• Dynamic monopolies with randomized starting configuration

Cited In (13)

• \(H\)-sequences and 2-step coreness in graphs
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• On subgraphs of bounded degeneracy in hypergraphs
• On dynamic monopolies of graphs with probabilistic thresholds
• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Remarks on dynamic monopolies with given average thresholds
• Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• Integer programming approach to static monopolies in graphs

This page was built for publication: Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444564)