Transversals of Vertex Partitions in Graphs
Copyright policy )Transversals of Vertex Partitions in Graphs
This paper studies a number of graph-theoretic parameters that are defined by statements of the form: For every partition of the vertex set that satisfies an upper (or lower) bound on the number of elements in each partition class, there is a transveral of the partition that is an independent (or dominating) set. A possible application to fault-tolerant data storage for the parameter ''partition independence number'' is discussed, and bounds for the parameters that are functions of minimum and maximum degree are given. The complexity of a related computational problem is also studied.
Coloring of graphs and hypergraphs, transversal, Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, Generalized Ramsey theory, fault-tolerant data storage, complexity
Coloring of graphs and hypergraphs, transversal, Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, Generalized Ramsey theory, fault-tolerant data storage, complexity
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).29 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!