{"@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/Q799696","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q799696","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q799696","kernelVersion":"v1","immutable":true,"modified":"2026-01-05T18:38:35Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q799696","name":"Upper bounds on the edge clique cover number of a graph","headline":"Upper bounds on the edge clique cover number of a graph","description":"scientific article; zbMATH DE number 3873378","url":"https://portal.mardi4nfdi.de/entity/Q799696","datePublished":"1984-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q624136"},{"@id":"https://portal.mardi4nfdi.de/entity/Q792342"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q175483"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0012-365X(84)90101-8","url":"https://doi.org/10.1016/0012-365X(84)90101-8"},"sameAs":["https://doi.org/10.1016/0012-365X(84)90101-8"],"comment":"For graphs without loops and multiple edges, let n be the number of nodes, k be the minimum number of cliques required to cover all the nodes, \\(\\bar k\\) be the minimum number of cliques required to cover all the edges, p be the minimum number of nodes such that every edge is incident with at least one of them, P be the maximum number of nodes such that no two are adjacent and E be the maximum number of edges such that no two are adjacent. The authors show that \\(\\bar k>pP\\) for almost all graphs and present several sufficient conditions for \\(\\bar k\\leq pP\\) to hold moreover they prove the following inequalities: \\(\\bar k\\leq k(n-k)\\) and \\(\\bar k\\leq E(n-E).\\)","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q3844890"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4187840"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3208702"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4111621"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1839263"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3318779"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5512009"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1324287"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4189303"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5539649"}]},"provenance":{"prov:generatedAtTime":"2026-01-05T18:38:35Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}