-
Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs [Elektronski vir]Boros, Endre ; Gurvich, Vladimir ; Milanič, Martin, 1980-A hypergraph is said to be 1-Sperner if for every twohyperedges the smallest of their two set differences is of size one. We present several applications of 1-Spernerhypergraphs to graphs. First, we ... consider several waysof associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, wecharacterize graphs yielding 1-Sperner hypergraphs.These results give new characterizations of threshold and domishold graphs. Second, we apply a characteriza-tion of 1-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, totaldomination, and connected domination.Source: Journal of graph theory [Elektronski vir]. - ISSN 1097-0118 (Vol. 94, no. 3, 2020, str. 364-397)Type of material - e-article ; adult, seriousPublish date - 2020Language - englishCOBISS.SI-ID - 1541798340
Author
Boros, Endre |
Gurvich, Vladimir |
Milanič, Martin, 1980-
Topics
1-Sperner hypergraph |
split |
bipartite, and cobipartite graphs |
threshold graphs |
vertex cover |
clique |
dominating set and closed neighborhood hypergraphs |
1-Spernerjev hipergraf |
omejena klična širina |
razcepljen graf |
dvodelen graf |
kodvodelen graf |
pragoven graf |
iz grafa izpeljan hipergraf
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Boros, Endre | ![]() |
Gurvich, Vladimir | ![]() |
Milanič, Martin, 1980- | 30211 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.