Search Results

1 - 10 of 13 items

  • Author: Michael A. Henning x
Clear All Modify Search
On Graphs with Disjoint Dominating and 2-Dominating Sets

Abstract

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the graph.

Open access
Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

Abstract

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G) ≤ γt2(G) ≤ γt(G). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.

Open access
Domination Game: Extremal Families for the 3/5-Conjecture for Forests

Abstract

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107] posted their 3/5-Conjecture that γg(G) ≤ ⅗n for every isolate-free forest on n vertices. Brešar, Klavžar, Košmrlj and Rall [Discrete Appl. Math. 161 (2013) 1308-1316] presented a construction that yields an infinite family of trees that attain the conjectured 3/5-bound. In this paper, we provide a much larger, but simpler, construction of extremal trees. We conjecture that if G is an isolate-free forest on n vertices satisfying γg(G) = ⅗n, then every component of G belongs to our construction.

Open access
A Characterization of Hypergraphs with Large Domination Number

Abstract

Let H = (V, E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D ⊆ V such that for every vertex v ∈ V \ D there exists an edge e ∈ E for which v ∈ e and e ∩ D ≠ ∅. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all edges of size at least k and with no isolated vertex, then γ(H) ≤ (n + ⌊(k − 3)/2⌋m)/(⌊3(k − 1)/2⌋). In this paper, we apply a recent result of the authors on hypergraphs with large transversal number [M.A. Henning and C. Löwenstein, A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem, Discrete Math. 323 (2014) 69-75] to characterize the hypergraphs achieving equality in this bound.

Open access
Bounds On The Disjunctive Total Domination Number Of A Tree

Abstract

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, γtd(G) , is the minimum cardinality of such a set. We observe that γtd(G)γt(G) . A leaf of G is a vertex of degree 1, while a support vertex of G is a vertex adjacent to a leaf. We show that if T is a tree of order n with leaves and s support vertices, then 2(n+3)/5γtd(T)(n+s1)/2 and we characterize the families of trees which attain these bounds. For every tree T, we show have γt(T)/γtd(T)<2 and this bound is asymptotically tight.

Open access
Graphs With Large Semipaired Domination Number

Abstract

Let G be a graph with vertex set V and no isolated vertices. A sub-set SV is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γpr2(G) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a connected graph G of order n ≥ 3, then γpr2(G)23n, and we characterize the extremal graphs achieving equality in the bound.

Open access
A Note on Non-Dominating Set Partitions in Graphs

Abstract

A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph G equals the total domination number of its complement G̅ and the minimum number of sets in a non-total dominating set partition of G equals the domination number of G̅ . This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.

Open access
Domination Parameters of a Graph and its Complement

Abstract

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

Open access
In silico selection approach to develop DNA aptamers for a stem-like cell subpopulation of non-small lung cancer adenocarcinoma cell line A549

Abstract

Background

Detection of circulating lung cancer cells with cancer-stem like characteristics would represent an improved tool for disease prognosis. However, current antibodies based methods have some disadvantages and therefore cell SELEX (Systematic Evolution of Ligands by Exponential Enrichment) was used to develop DNA aptamers, recognizing cell surface markers of non-small lung carcinoma (NSLC) cells.

Materials and methods

The human adenocarcinoma cell line A549 was used for selection in seven cell SELEX cycles. We used human blood leukocytes for negative selection, and lung stem cell protein marker CD90 antibody binding A549 cells for positive selection.

Results

The obtained oligonucleotide sequences after the seventh SELEX cycle were subjected to in silico selection analysis based on three independent types of bioinformatics approaches, selecting two closely related aptamer candidates in terms of consensus sequences, structural motifs, binding affinity (Kd) and stability (ΔG). We selected and identified the aptamer A155_18 with very good binding characteristics to A459 cells, selected for CD90 antibody binding. The calculated phylogenetic tree showed that aptamers A155_18 and the known A549 cell aptamer S6 have a close structural relationship. MEME sequence analysis showed that they share two unique motifs, not present in other sequences.

Conclusions

The novel aptamer A155_18 has strong binding affinity for A549 lung carcinoma cell line subpopulation that is expressing stem cell marker CD90, indicating a possible stemness, characteristic for the A459 line, or a subpopulation present within this cell line. This aptamer can be applied as diagnostic tool, identifying NSLC circulating cells.

Open access
Hereditary Equality of Domination and Exponential Domination

Abstract

We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G.

Open access