Search

Do\v{s}li\'{c} et al. defined the Mostar index of a graph $G$ as $Mo(G)=\sum\limits_{uv\in E(G)}|n_G(u,v)-n_G(v,u)|$, where, for an edge $uv$ of $G$, the term $n_G(u,v)$ denotes the number of vertices of $G$ that have a smaller distance in $G$ to $u$ than to $v$. For a graph $G$ of order $n$ and maximum degree at most $\Delta$, we show $Mo(G)\leq \frac{\Delta}{2}n^2-(1-o(1))c_{\Delta}n\log(\log(n)),$ where $c_{\Delta}>0$ only depends on $\Delta$ and the $o(1)$ term only depends on $n$. Furthermore, for integers $n_0$ and $\Delta$ at least $3$, we show the existence of a $\Delta$-regular graph of order $n$ at least $n_0$ with $Mo(G)\geq \frac{\Delta}{2}n^2-c'_{\Delta}n\log(n),$ where $c'_{\Delta}>0$ only depends on $\Delta$.

A set $D$ of vertices is a strong dominating set in a graph $G$, if for every vertex $x\in V(G) \setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $deg(x) \leq deg(y)$. The strong domination number $\gamma_{st}(G)$ of $G$ is the minimum cardinality of a strong dominating set in $G$. Let $G$ be a connected graph constructed from pairwise disjoint connected graphs $G_1,\ldots ,G_k$ by selecting a vertex of $G_1$, a vertex of $G_2$, and identifying these two vertices, and thereafter continuing in this manner inductively. The graphs $G_1,\ldots ,G_k$ are the primary subgraphs of $G$. In this paper, we study the strong domination number of $K_r$-gluing of two graphs and investigate the strong domination number for some particular cases of graphs from their primary subgraphs., Comment: 20 pages, 13 figures

Let $G$ be graph with vertex set $V$ and order $n=|V|$. A coalition in $G$ is a combination of two distinct sets, $A\subseteq V$ and $B\subseteq V$, which are disjoint and are not dominating sets of $G$, but $A\cup B$ is a dominating set of $G$. A coalition partition of $G$ is a partition $\mathcal{P}=\{S_1,\ldots,S_k\}$ of its vertex set $V$, where each set $S_i\in \mathcal{P}$ is either a dominating set of $G$ with only one vertex, or it is not a dominating set but forms a coalition with some other set $S_j \in \mathcal{P}$. The coalition number $C(G)$ is the maximum cardinality of a coalition partition of $G$. To represent a coalition partition $\mathcal{P}$ of $G$, a coalition graph $\CG(G, \mathcal{P})$ is created, where each vertex of the graph corresponds to a member of $\mathcal{P}$ and two vertices are adjacent if and only if their corresponding sets form a coalition in $G$. A coalition partition $\mathcal{P}$ of $G$ is a singleton coalition partition if every set in $\mathcal{P}$ consists of a single vertex. If a graph $G$ has a singleton coalition partition, then $G$ is referred to as a singleton-partition graph. A graph $H$ is called a singleton coalition graph of a graph $G$ if there exists a singleton coalition partition $\mathcal{P}$ of $G$ such that the coalition graph $\CG(G,\mathcal{P})$ is isomorphic to $H$. A singleton coalition graph chain with an initial graph $G_1$ is defined as the sequence $G_1\rightarrow G_2\rightarrow G_3\rightarrow\cdots$ where all graphs $G_i$ are singleton-partition graphs, and $\CG(G_i,\Gamma_1)=G_{i+1}$, where $\Gamma_1$ represents a singleton coalition partition of $G_i$. In this paper, we address two open problems posed by Haynes et al. We characterize all graphs $G$ of order $n$ and minimum degree $\delta(G)=2$ such that $C(G)=n$ and investigate the singleton coalition graph chain starting with graphs $G$ where $\delta(G)\le 2$.

Let $G=(V,E)$ be a graph with no isolated vertices. A vertex $v$ totally dominate a vertex $w$ ($w \ne v$), if $v$ is adjacent to $w$. A set $D \subseteq V$ called a total dominating set of $G$ if every vertex $v\in V$ is totally dominated by some vertex in $D$. The minimum cardinality of a total dominating set is the total domination number of $G$ and is denoted by $\gamma_t(G)$. A total dominator coloring of graph $G$ is a proper coloring of vertices of $G$, so that each vertex totally dominates some color class. The total dominator chromatic number $\chi_{td}(G)$ of $G$ is the least number of colors required for a total dominator coloring of $G$. The Total Dominator Coloring problem is to find a total dominator coloring of $G$ using the minimum number of colors. It is known that the decision version of this problem is NP-complete for general graphs. We show that it remains NP-complete even when restricted to bipartite, planar and split graphs. We further study the Total Dominator Coloring problem for various graph classes, including trees, cographs and chain graphs. First, we characterize the trees having $\chi_{td}(T)=\gamma_t(T)+1$, which completes the characterization of trees achieving all possible values of $\chi_{td}(T)$. Also, we show that for a cograph $G$, $\chi_{td}(G)$ can be computed in linear-time. Moreover, we show that $2 \le \chi_{td}(G) \le 4$ for a chain graph $G$ and give characterization of chain graphs for every possible value of $\chi_{td}(G)$ in linear-time., Comment: V1, 18 pages, 1 figure

A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The total domination number, γt(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [J. Combin. Math. Combin. Comput. 58 (2006), 189-193] showed that if T is a nontrivial tree of order n, with ℓ leaves, then γt(T) = ⌈(n - ℓ+2)/2⌉. In this paper, we first characterize all trees T of order n with ℓ leaves satisfying γt(T) = ⌈(n - ℓ+2)=2⌉. We then generalize this result to connected graphs and show that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and ℓ leaves, then γ](G) ≥ ⌈(n-ℓ+2)=2⌉ - k. We also characterize the graphs G achieving equality for this new bound.

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of $V(G) \setminus S$ is adjacent to a vertex in $S$. A coalition in $G$ consists of two disjoint sets of vertices $X$ and $Y$ of $G$, neither of which is a dominating set but whose union $X \cup Y$ is a dominating set of $G$. Such sets $X$ and $Y$ form a coalition in $G$. A coalition partition, abbreviated $c$-partition, in $G$ is a partition $\mathcal{X} = \{X_1,\ldots,X_k\}$ of the vertex set $V(G)$ of $G$ such that for all $i \in [k]$, each set $X_i \in \mathcal{X}$ satisfies one of the following two conditions: (1) $X_i$ is a dominating set of $G$ with a single vertex, or (2) $X_i$ forms a coalition with some other set $X_j \in \mathcal{X}$. %The coalition number ${C}(G)$ is the maximum cardinality of a $c$-partition of $G$. Let ${\cal A} = \{A_1,\ldots,A_r\}$ and ${\cal B}= \{B_1,\ldots, B_s\}$ be two partitions of $V(G)$. Partition ${\cal B}$ is a refinement of partition ${\cal A}$ if every set $B_i \in {\cal B} $ is either equal to, or a proper subset of, some set $A_j \in {\cal A}$. Further if ${\cal A} \ne {\cal B}$, then ${\cal B}$ is a proper refinement of ${\cal A}$. Partition ${\cal A}$ is a minimal $c$-partition if it is not a proper refinement of another $c$-partition. Haynes et al. [AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653--659] defined the minmin coalition number $c_{\min}(G)$ of $G$ to equal the minimum order of a minimal $c$-partition of $G$. We show that $2 \le c_{\min}(G) \le n$, and we characterize graphs $G$ of order $n$ satisfying $c_{\min}(G) = n$. A polynomial-time algorithm is given to determine if $c_{\min}(G)=2$ for a given graph $G$. A necessary and sufficient condition for a graph $G$ to satisfy $c_{\min}(G) \ge 3$ is given, and a characterization of graphs $G$ with minimum degree~$2$ and $c_{\min}(G)= 4$ is provided.

A graph is $\alpha$-excellent if every vertex of the graph is contained in some maximum independent set of the graph. In this paper, we present two characterizations of the $\alpha$-excellent $2$-trees., Comment: 10 pages, 3 figures

A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex that does not belong to $S$ is adjacent to a vertex in $S$. The domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. The common independence number $\alpha_c(G)$ of $G$ is the greatest integer $r$ such that every vertex of $G$ belongs to some independent set of cardinality at least~$r$. The common independence number is squeezed between the independent domination number $i(G)$ and the independence number $\alpha(G)$ of $G$, that is, $\gamma(G) \le i(G) \le \alpha_c(G) \le \alpha(G)$. A graph $G$ is domination perfect if $\gamma(H) = i(H)$ for every induced subgraph $H$ of $G$. We define a graph $G$ as common domination perfect if $\gamma(H) = \alpha_c(H)$ for every induced subgraph $H$ of $G$. We provide a characterization of common domination perfect graphs in terms of ten forbidden induced subgraphs., Comment: 11 pages, 2 figures

Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $S\subseteq V$ such that every vertex not in $S$ is adjacent to at least one vertex in $S$. The cardinality of a smallest dominating set of $G$, denoted by $\gamma(G)$, is the domination number of $G$. Two vertices are neighbors if they are adjacent. A super dominating set is a dominating set $S$ with the additional property that every vertex in $V \setminus S$ has a neighbor in $S$ that is adjacent to no other vertex in $V \setminus S$. Moreover if every vertex in $V \setminus S$ has degree at least~$2$, then $S$ is an end super dominating set. The end super domination number is the minimum cardinality of an end super dominating set. We give applications of end super dominating sets as main servers and temporary servers of networks. We determine the exact value of the end super domination number for specific classes of graphs, and we count the number of end super dominating sets in these graphs. Tight upper bounds on the end super domination number are established, where the graph is modified by vertex (edge) removal and contraction., Comment: 25 pages, 11 figures

We study upper bounds on the size of optimum locating-total dominating sets in graphs. A set $S$ of vertices of a graph $G$ is a locating-total dominating set if every vertex of $G$ has a neighbor in $S$, and if any two vertices outside $S$ have distinct neighborhoods within $S$. The smallest size of such a set is denoted by $\gamma^L_t(G)$. It has been conjectured that $\gamma^L_t(G)\leq\frac{2n}{3}$ holds for every twin-free graph $G$ of order $n$ without isolated vertices. We prove that the conjecture holds for cobipartite graphs, split graphs, block graphs, subcubic graphs and outerplanar graphs.

Let H be a hypergraph of order nH= |V(/H)| and size mH= |E(H)|. The transversal number τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A k-uniform hypergraph has all edges of size k. For k ≥ 2, let Lkdenote the class of k-uniform linear hypergraphs. We consider the problem of determining the best possible constants qk(which depends only on k) such that τ(H) < qk{nH+mH) for all H ∈ Lk. It is known that q2= 1/3 and q3= 1/4. In this paper we show that q4= 1/5, which is better than for non-linear hypergraphs. Using the affine plane AG(2,4) of order 4, we show there are a large number of densities of hypergraphs H ∈ L4such that τ(H) ≈ 1/5{nH+ mH).

We define a $P$-compelling coloring as a proper coloring of the vertices of a graph such that every subset consisting of one vertex of each color has property $P$. The $P$-compelling chromatic number is the minimum number of colors in such a coloring. We show that this notion generalizes the dominator and total dominator chromatic numbers, and provide some general bounds and algorithmic results. We also investigate the specific cases where $P$ is that the subset contains at least one edge or that the subset is connected.

A subset $D\subseteq V_G$ is a dominating set of $G$ if every vertex in $V_G\setminus D$ has a neighbor in $D$, while $D$ is a 2-dominating set of $G$ if every vertex belonging to $V_G\setminus D$ is joined by at least two edges with a vertex or vertices in $D$. A graph $G$ is a $(2,2)$-dominated graph if it has a pair $(D,D')$ of disjoint $2$-dominating sets of vertices of $G$. In this paper we present two characterizations of minimal $(2,2)$-dominated graphs., Comment: 8 pages, 4 figures

TxGraffiti is an automated conjecturing program that produces graph theoretic conjectures in the form of conjectured inequalities. This program written and maintained by the second author since 2017 was inspired by the successes of previous automated conjecturing programs including Fajtlowicz's GRAFFITI and DeLaVi\~{n}a's GRAFFITI.pc. In this paper we prove and generalize several conjectures generated by TxGraffiti when it was prompted to conjecture on the \emph{independence number}, the \emph{domination number}, and the \emph{matching number} (and generalizations of each of these graph invariants). Moreover, in several instances we also show the proposed inequalities relating these graph invariants are sharp.

Maker-Breaker total domination game in graphs is introduced as a natural counterpart to the Maker-Breaker domination game recently studied by Duch\^ene, Gledel, Parreau, and Renault. Both games are instances of the combinatorial Maker-Breaker games. The Maker-Breaker total domination game is played on a graph $G$ by two players who alternately take turns choosing vertices of $G$. The first player, Dominator, selects a vertex in order to totally dominate $G$ while the other player, Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. It is shown that there are infinitely many connected cubic graphs in which Staller wins and that no minimum degree condition is sufficient to guarantee that Dominator wins when Staller starts the game. An amalgamation lemma is established and used to determine the outcome of the game played on grids. Cacti are also classified with respect to the outcome of the game. A connection between the game and hypergraphs is established. It is proved that the game is PSPACE-complete on split and bipartite graphs. Several problems and questions are also posed., Comment: 21 pages, 5 figures

We propose the conjecture that every tree with order $n$ at least $2$ and total domination number $\gamma_t$ has at most $\left(\frac{n-\frac{\gamma_t}{2}}{\frac{\gamma_t}{2}}\right)^{\frac{\gamma_t}{2}}$ minimum total dominating sets. As a relaxation of this conjecture, we show that every forest $F$ with order $n$, no isolated vertex, and total domination number $\gamma_t$ has at most $\min\left\{\left(8\sqrt{e}\, \right)^{\gamma_t}\left(\frac{n-\frac{\gamma_t}{2}}{\frac{\gamma_t}{2}}\right)^{\frac{\gamma_t}{2}}, (1+\sqrt{2})^{n-\gamma_t},1.4865^n\right\}$ minimum total dominating sets., Discrete Mathematics & Theoretical Computer Science ; Vol. 21 no. 3 ; 1365-8050

The zero forcing number of a simple graph, written $Z(G)$, is a NP-hard graph invariant which is the result of the zero forcing color change rule. This graph invariant has been heavily studied by linear algebraists, physicists, and graph theorist. It's broad applicability and interesting combinatorial properties have attracted the attention of many researchers. Of particular interest, is that of bounding the zero forcing number from above. In this paper we show a surprising relation between the zero forcing number of a graph and the independence number of a graph, denoted $\alpha(G)$. Our main theorem states that if $G \ne K_4$ is a connected, cubic, claw-free graph, then $Z(G) \le \alpha(G) + 1$. This improves on best known upper bounds for $Z(G)$, as well as known lower bounds on $\alpha(G)$. As a consequence of this result, if $G \ne K_4$ is a connected, cubic, claw-free graph with order $n$, then $Z(G) \le \frac{2}{5}n + 1$. Additionally, under the hypothesis of our main theorem, we further show $Z(G) \le \alpha'(G)$, where $\alpha'(G)$ denotes the matching number of $G$.

The transversal number $\tau(H)$ of a hypergraph $H$ is the minimum number of vertices that intersect every edge of $H$. A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A $k$-uniform hypergraph has all edges of size $k$. It is known that $\tau(H) \le (n + m)/(k+1)$ holds for all $k$-uniform, linear hypergraphs $H$ when $k \in \{2,3\}$ or when $k \ge 4$ and the maximum degree of $H$ is at most two. It has been conjectured that $\tau(H) \le (n+m)/(k+1)$ holds for all $k$-uniform, linear hypergraphs $H$. We disprove the conjecture for large $k$, and show that the best possible constant $c_k$ in the bound $\tau(H) \le c_k (n+m)$ has order $\ln(k)/k$ for both linear (which we show in this paper) and non-linear hypergraphs. We show that for those $k$ where the conjecture holds, it is tight for a large number of densities if there exists an affine plane $AG(2,k)$ of order $k \ge 2$. We raise the problem to find the smallest value, $k_{\min}$, of $k$ for which the conjecture fails. We prove a general result, which when applied to a projective plane of order $331$ shows that $k_{\min} \le 166$. Even though the conjecture fails for large $k$, our main result is that it still holds for $k=4$, implying that $k_{\min} \ge 5$. The case $k=4$ is much more difficult than the cases $k \in \{2,3\}$, as the conjecture does not hold for general (non-linear) hypergraphs when $k=4$. Key to our proof is the completely new technique of the deficiency of a hypergraph introduced in this paper., Comment: 105 pages

Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a neighboring vertex to an attacked vertex (we assume attacks happen only at vertices containing no guard and that each vertex contains at most one guard). More than one guard is allowed to move in response to an attack. The $m$-eternaldomination number, $\edom(G)$, of a graph $G$ is the minimum number of guards needed to defend $G$ against any such sequence. We show that if $G$ is a connected graph with minimum degree at least~$2$ and of order~$n \ge 5$, then $\edom(G) \le \left\lfloor \frac{n-1}{2} \right\rfloor$, and this bound is tight. We also prove that if $G$ is a cubic bipartite graph of order~$n$, then $\edom(G) \le \frac{7n}{16}$., Contributions to Discrete Mathematics, Vol 12, No 2 (2017)

A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a $2$-independent set if every vertex in $S$ is adjacent to at most one vertex of $S$. The $2$-domination number $\gamma_2(G)$ is the minimum cardinality of a $2$-dominating set in $G$, and the $2$-independence number $\alpha_2(G)$ is the maximum cardinality of a $2$-independent set in $G$. Chellali and Meddah [{\it Trees with equal $2$-domination and $2$-independence numbers,} Discussiones Mathematicae Graph Theory 32 (2012), 263--270] provided a constructive characterization of trees with equal $2$-domination and $2$-independence numbers. Their characterization is in terms of global properties of a tree, and involves properties of minimum $2$-dominating and maximum $2$-independent sets in the tree at each stage of the construction. We provide a constructive characterization that relies only on local properties of the tree at each stage of the construction., Comment: 17 pages, 4 figures

Let $G$ be a simple and finite graph without isolated vertices. In this paper we study forcing sets (zero forcing sets) which induce a subgraph of $G$ without isolated vertices. Such a set is called a total forcing set, introduced and first studied by Davila \cite{Davila}. The minimum cardinality of a total forcing set in $G$ is the total forcing number of $G$, denoted $F_t(G)$. We study basic properties of $F_t(G)$, relate $F_t(G)$ to various domination parameters, and establish $NP$-completeness of the associated decision problem for $F_t(G)$. We also prove that if $G$ is a connected graph of order $n \ge 3$ and maximum degree $\Delta$, then $F_t(G) \le ( \frac{\Delta}{\Delta +1} ) n$, with equality if and only if $G$ is a complete graph $K_{\Delta + 1}$.

A dynamic coloring of the vertices of a graph $G$ starts with an initial subset $S$ of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set $S$ is called a forcing set (zero forcing set) of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes colored. If the initial set $S$ has the added property that it induces a subgraph of $G$ without isolated vertices, then $S$ is called a total forcing set in $G$. The total forcing number of $G$, denoted $F_t(G)$, is the minimum cardinality of a total forcing set in $G$. We prove that if $G$ is a connected cubic graph of order~$n$ that has a spanning $2$-factor consisting of triangles, then $F_t(G) \le \frac{1}{2}n$. More generally, we prove that if $G$ is a connected, claw-free, cubic graph of order~$n \ge 6$, then $F_t(G) \le \frac{1}{2}n$, where a claw-free graph is a graph that does not contain $K_{1,3}$ as an induced subgraph. The graphs achieving equality in these bounds are characterized.

In the total domination game played on a graph $G$, players Dominator and Staller alternately select vertices of $G$, as long as possible, such that each vertex chosen increases the number of vertices totally dominated. Dominator (Staller) wishes to minimize (maximize) the number of vertices selected. The game total domination number, $\gamma_{\rm tg}(G)$, of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. If a vertex $v$ of $G$ is declared to be already totally dominated, then we denote this graph by $G|v$. In this paper the total domination game critical graphs are introduced as the graphs $G$ for which $\gamma_{\rm tg}(G|v) < \gamma_{\rm tg}(G)$ holds for every vertex $v$ in $G$. If $\gamma_{\rm tg}(G) = k$, then $G$ is called $k$-$\gamma_{\rm tg}$-critical. It is proved that the cycle $C_n$ is $\gamma_{{\rm tg}}$-critical if and only if $n\pmod 6 \in \{0,1,3\}$ and that the path $P_n$ is $\gamma_{{\rm tg}}$-critical if and only if $n\pmod 6\in \{2,4\}$. $2$-$\gamma_{\rm tg}$-critical and $3$-$\gamma_{\rm tg}$-critical graphs are also characterized as well as $3$-$\gamma_{\rm tg}$-critical joins of graphs.

In this paper, we continue the study of $2$-colorings in hypergraphs. A hypergraph is $2$-colorable if there is a $2$-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen [J. Amer. Math. Soc. 5 (1992), 217--229]) that every $4$-uniform $4$-regular hypergraph is $2$-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph $H$ to be a free vertex in $H$ if we can $2$-color $V(H) \setminus \{v\}$ such that every hyperedge in $H$ contains vertices of both colors (where $v$ has no color). We prove that every $4$-uniform $4$-regular hypergraph has a free vertex. This proves a known conjecture. Our proofs use a new result on not-all-equal $3$-SAT which is also proved in this paper and is of interest in its own right., 14 pages

In this paper, we study a dynamic coloring of the vertices of a graph $G$ that starts with an initial subset $S$ of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set $S$ is called a forcing set of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes colored. The forcing number, originally known as the \emph{zero forcing number}, and denoted $F(G)$, of $G$ is the cardinality of a smallest forcing set of $G$. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth $g$ of a graph is the length of a shortest cycle in the graph. Let $G$ be a graph with minimum degree $\delta \ge 2$ and girth~$g \ge 3$. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that $F(G) \ge \delta + (\delta-2)(g-3)$. This conjecture has recently been proven for $g \le 6$. The conjecture is also proven when the girth $g \ge 7$ and the minimum degree is sufficiently large. In particular, it holds when $g = 7$ and $\delta \ge 481$, when $g = 8$ and $\delta \ge 649$, when $g = 9$ and $\delta \ge 30$, and when $g = 10$ and $\delta \ge 34$. In this paper, we prove the conjecture for $g \in \{7,8,9,10\}$ and for all values of $\delta \ge 2$.

We consider (not necessarily proper) colorings of the vertices of a graph where every color is thoroughly distributed, that is, appears in every open neighborhood. Equivalently, every color is a total dominating set. We define $\td(G)$ as the maximum number of colors in such a coloring and $\FTD(G)$ as the fractional version thereof. In particular, we show that every claw-free graph with minimum degree at least~$2$ has~$\FTD(G)\ge 3/2$ and this is best possible. For planar graphs, we show that every triangular disc has $\FTD(G) \ge 3/2$ and this is best possible, and that every planar graph has $\td(G) \le 4$ and this is best possible, while we conjecture that every planar triangulation has $\td(G)\ge 2$. Further, although there are arbitrarily large examples of connected, cubic graphs with $\td(G)=1$, we show that for a connected cubic graph $\FTD(G) \ge 2-o(1)$, and conjecture that it is always at least~$2$. We also consider the related concepts in hypergraphs., 26 pages

In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph.

International audience; A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by inline image, is the minimum cardinality of an independent dominating set. In this article, we show that if inline image is a connected cubic graph of order n that does not have a subgraph isomorphic to K2, 3, then inline image. As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then inline image, where inline image denotes the domination number of G.

A graph G is diameter 2-critical if its diameter is two, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.

Let $G$ be a graph with no isolated vertex. A matching in $G$ is a set of edges that are pairwise not adjacent in $G$, while the matching number, $\alpha'(G)$, of $G$ is the maximum size of a matching in $G$. The path covering number, $\rm{pc}(G)$, of $G$ is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if $G$ has order $n$, then $\alpha'(G) + \frac{1}{2}\rm{pc}(G) \ge \frac{n}{2}$ and we provide a constructive characterization of the graphs achieving equality in this bound. It is known that $\gamma(G) \le \alpha'(G)$ and $\gamma_t(G) \le \alpha'(G) + \rm{pc}(G)$, where $\gamma(G)$ and $\gamma_t(G)$ denote the domination and the total domination number of $G$. As an application of our result on the matching and path cover numbers, we show that if $G$ is a graph with $\delta(G) \ge 3$, then $\gamma_t(G) \le \alpha'(G) + \frac{1}{2}(\rm{pc}(G) - 1)$, and this bound is tight. A set $S$ of vertices in $G$ is a neighborhood total dominating set of $G$ if it is a dominating set of $G$ with the property that the subgraph induced by the open neighborhood of the set $S$ has no isolated vertex. The neighborhood total domination number, $\gamma_{\rm nt}(G)$, is the minimum cardinality of a neighborhood total dominating set of $G$. We observe that $\gamma(G) \le \gamma_{\rm nt}(G) \le \gamma_t(G)$. As a further application of our result on the matching and path cover numbers, we show that if $G$ is a connected graph on at least six vertices, then $\gamma_{\rm nt}(G) \le \alpha'(G) + \frac{1}{2}\rm{pc}(G)$ and this bound is tight.

In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of $G$. Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set $S$ of $G$ in which every vertex is totally dominated by a vertex in $S$. Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, $\gamma_{\rm tg}(G)$, of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. Henning, Klav\v{z}ar and Rall [Combinatorica, to appear] posted the $\frac{3}{4}$-Game Total Domination Conjecture that states that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $\gamma_{\rm tg}(G) \le \frac{3}{4}n$. In this paper, we prove this conjecture over the class of graphs $G$ that satisfy both the condition that the degree sum of adjacent vertices in $G$ is at least $4$ and the condition that no two vertices of degree $1$ are at distance $4$ apart in $G$. In particular, we prove that by adopting a greedy strategy, Dominator can complete the total domination game played in a graph with minimum degree at least $2$ in at most $3n/4$ moves., Comment: 14 pages

We show that a cubic graph $G$ of order $n$ has an induced $2$-regular subgraph of order at least a) $\frac{n-2}{4-\frac{4}{k}}$, if $G$ has no induced cycle of length more than $k$, b) $\frac{5n+6}{8}$, if $G$ has no induced cycle of length more than $4$, and $n>6$, and c) $\left(\frac{1}{4}+\epsilon\right)n$, if the independence number of $G$ is at most $\left(\frac{3}{8}-\epsilon\right)n$. To show the second result we give a precise structural description of cubic $4$-chordal graphs., Comment: 10 pages

A matching in a hypergraph H is a set of pairwise vertex disjoint edges in H and the matching number of H is the maximum cardinality of a matching in H. A hypergraph H is an intersecting hypergraph if every two distinct edges of H have a non-empty intersection. Equivalently, H is an intersecting hypergraph if and only if it has matching number one. In this paper, we study intersecting hypergraphs that are matching critical in the sense that the matching number increases under various de nitions of criticality.Keywords: Transversals, matchings, hypergraphs, projective planeQuaestiones Mathematicae 37(2014), 127-138

For $k \ge 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. The transversal number $\tau(H)$ of $H$ is the minimum number of vertices that intersect every edge. Chv\'{a}tal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $\tau(H)\le ( n + \left\lfloor \frac k2 \right\rfloor m )/ ( \left\lfloor \frac{3k}2 \right\rfloor )$. When $k = 3$, the connected hypergraphs that achieve equality in the Chv\'{a}tal-McDiarmid Theorem were characterized by Henning and Yeo [J. Graph Theory 59 (2008), 326--348]. In this paper, we characterize the connected hypergraphs that achieve equality in the Chv\'{a}tal-McDiarmid Theorem for $k = 2$ and for all $k \ge 4$., Comment: 12 pages

For $k \ge 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. The transversal number $��(H)$ of $H$ is the minimum number of vertices that intersect every edge. Chv��tal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $��(H)\le ( n + \left\lfloor \frac k2 \right\rfloor m )/ ( \left\lfloor \frac{3k}2 \right\rfloor )$. When $k = 3$, the connected hypergraphs that achieve equality in the Chv��tal-McDiarmid Theorem were characterized by Henning and Yeo [J. Graph Theory 59 (2008), 326--348]. In this paper, we characterize the connected hypergraphs that achieve equality in the Chv��tal-McDiarmid Theorem for $k = 2$ and for all $k \ge 4$., 12 pages

International audience; A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γpr (G). We establish bounds on Γpr (G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γpr (G) ≤ 4n/5 if δ = 1 and n ≥ 3, Γpr (G) ≤ 3n/4 if δ = 2 and n ≥ 6, and Γpr (G) ≤ 2n/3 if δ ≥ 3. All these bounds are sharp. Further, if n ≥ 6 the graphs G achieving the bound Γpr (G) = 4n/5 are characterized, while for n ≥ 9 the graphs G with δ = 2 achieving the bound Γpr (G) = 3n/4 are characterized.

Let G = (V, E) be a graph with no isolated vertex. A classical observation in domination theory is that if D is a minimum dominating set of G, then V \ D is also a dominating set of G. A set D' is an inverse dominating set of G if D' is a dominating set of G and D' subset of V \ D for some minimum dominating set D of G. The inverse domination number of G is the minimum cardinality among all inverse dominating sets of G. The independence number of G is the maximum cardinality of an independent set of vertices in G. Domke, Dunbar, and Markus (Ars Combin. 72 (2004), 149-160) conjectured that the inverse domination number of G is at most the independence number of G. We prove this conjecture for special families of graphs, including claw-free graphs, bipartite graphs, split graphs, very well covered graphs, chordal graphs and cactus graphs.

Let G = (V,E) be a graph with no isolated vertex. A classical observation in domination theory is that if D is a minimum dominating set of G, then V \D is also a dominating set of G. A set D′ is an inverse dominating set of G if D′ is a dominating set of G and D′ ⊆ V \D for some minimum dominating set D of G. The inverse domination number of G is the minimum cardinality among all inverse dominating sets of G. The independence number of G is the maximum cardinality of an independent set of vertices in G. Domke, Dunbar, and Markus (Ars Combin. 72 (2004), 149-160) conjectured that the inverse domination number of G is at most the independence number of G. We prove this conjecture for special families of graphs, including claw-free graphs, bipartite graphs, split graphs, very well covered graphs, chordal graphs and cactus graphs. Let G = (V,E) be a graph with no isolated vertex. A classical observation in domination theory is that if D is a minimum dominating set of G, then V \D is also a dominating set of G. A set D′ is an inverse dominating set of G if D′ is a dominating set of G and D′ ⊆ V \D for some minimum dominating set D of G. The inverse domination number of G is the minimum cardinality among all inverse dominating sets of G. The independence number of G is the maximum cardinality of an independent set of vertices in G. Domke, Dunbar, and Markus (Ars Combin. 72 (2004), 149-160) conjectured that the inverse domination number of G is at most the independence number of G. We prove this conjecture for special families of graphs, including claw-free graphs, bipartite graphs, split graphs, very well covered graphs, chordal graphs and cactus graphs.

Udgivelsesdato: NOV

Ziel dieser Arbeit war die Untersuchung, inwieweit sich die Expression bestimmter Oberflächenmerkmale auf Lymphozyten im peripheren Blut nach einer Transplantation im Rahmen der chronischen Abstoßungsreaktion verändert. Dazu wurde ein etabliertes Modell zur chronischen Abstoßung mit zwei sich genetisch nur gering differierenden Rattenspezies verwendet. Dabei wurden Herzen von Lewis-Ratten heterotop auf Fischer 344-Ratten transplantiert. Die Untersuchung wurde vergleichend unter der immunsuppressiven Behandlung von Cyclosporin A (CsA), Tacrolimus (FK-506) und Mycophenolate mofetil (MMF) sowie einer unbehandelten Gruppe durchgeführt. Über den Zeitraum von 60 Tagen wurden die Oberflächenmerkmale mit durchflusszytometrischen Messungen bestimmt.