{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q686272","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q686272","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q686272","kernelVersion":"v1","immutable":true,"modified":"2025-12-31T23:24:26Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q686272","name":"Extremal graphs domination insensitive to the removal of \\(k\\) edges","headline":"Extremal graphs domination insensitive to the removal of \\(k\\) edges","description":"scientific article; zbMATH DE number 428119","url":"https://portal.mardi4nfdi.de/entity/Q686272","datePublished":"1993-11-28","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q234392"},{"@id":"https://portal.mardi4nfdi.de/entity/Q624136"},{"@id":"https://portal.mardi4nfdi.de/entity/Q792342"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q96294"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0166-218X(93)90238-J","url":"https://doi.org/10.1016/0166-218X(93)90238-J"},"sameAs":["https://doi.org/10.1016/0166-218X(93)90238-J"],"comment":"The domination number \\(\\gamma(G)\\) of a graph \\(G\\) is the minimum number of vertices of a dominating set in \\(G\\), i.e. a subset \\(D\\) of the vertex set \\(V(G)\\) of \\(G\\) such that for each \\(x \\in V(G)-D\\) there exists \\(y \\in D\\) adjacent to \\(x\\). A graph \\(G\\) is called \\(\\gamma_ k\\)-insensitive, if \\(\\gamma(G)\\) remains the same after removing arbitrary \\(k\\) edges from \\(G\\). The minimum number of edges of a \\(\\gamma_ k\\)-insensitive graph with \\(p\\) vertices and the domatic number \\(\\gamma\\) is denoted by \\(E^ k(p,\\gamma)\\). For \\(k=1\\) this number was determined in a previous paper of two of the authors of this paper.   In the present paper the exact value is determined for \\(E^ k(p,1)\\) and lower and upper bounds are given for \\(E^ k(p,\\gamma)\\) in general. In the case \\(k+1\\leq \\gamma \\leq 2k\\) the value of \\(E^ k(p,\\gamma)\\) is proved to be asymptotically equal to \\((k+3)p/2\\). Some properties of \\(\\gamma_ k\\)-insensitive graphs are described.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q585222"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3807242"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3472129"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3983241"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1099185"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1096642"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4346786"},{"@id":"https://portal.mardi4nfdi.de/entity/Q689974"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1324287"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4750666"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3728935"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4014294"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4009711"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3472128"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5284032"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4024335"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4729819"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4206379"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5917319"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5906153"}]},"provenance":{"prov:generatedAtTime":"2025-12-31T23:24:26Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}