Independent face and vertex covers in plane graphs
A set S ⊆ V of vertices in a graph G = (V, E) is called a dominating set if every vertex in V-S is adjacent to a vertex in S. A dominating set which intersects every maximum independent set in G is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by . In this paper we begin an investigation of this parameter.
We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.
We show that if a colouring c establishes ω₂ ↛ [(ω₁:ω)]² then c establishes this negative partition relation in each Cohen-generic extension of the ground model, i.e. this property of c is Cohen-indestructible. This result yields a negative answer to a question of Erdős and Hajnal: it is consistent that GCH holds and there is a colouring c:[ω₂]² → 2 establishing ω₂ ↛ [(ω₁:ω)]₂ such that some colouring g:[ω₁]² → 2 does not embed into c. It is also consistent that is arbitrarily large, and there...
Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from Ϟ(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b*or b* + 1, where b* = ⌊2(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 1 is not within a distance of w(n)/(ln...
A subset of the vertex set of a graph is called dominating in , if each vertex of either is in , or is adjacent to a vertex of . If moreover the subgraph of induced by is regular of degree 1, then is called an induced-paired dominating set in . A partition of , each of whose classes is an induced-paired dominating set in , is called an induced-paired domatic partition of . The maximum number of classes of an induced-paired domatic partition of is the induced-paired domatic...
Let be a nonincreasing sequence of positive real numbers. Denote by the index set and by , the set of all subsets of of cardinality , . In addition, denote by , , , the sum of arbitrary elements of sequence , where and . We consider bounds of the quantities , and in terms of and . Then we use the obtained results to generalize some results regarding Laplacian and normalized Laplacian eigenvalues of graphs.
Let be an integer-valued function defined on the vertex set of a graph . A subset of is an -dominating set if each vertex outside is adjacent to at least vertices in . The minimum number of vertices in an -dominating set is defined to be the -domination number, denoted by . In a similar way one can define the connected and total -domination numbers and . If for all vertices , then these are the ordinary domination number, connected domination number and total domination...