A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number for some families...

The total edge-domatic number of a graph is introduced as an edge analogue of the total domatic number. Its values are studied for some special classes of graphs. The concept of totally edge-domatically full graph is introduced and investigated.

Dans cet article on étudie les propriétés d’ordres totaux à distance minimum d’un ensemble de tournois ; on montre, par exemple, que ces ordres contiennent l’ordre d’unanimité. On étudie la fonction $f(n,v)$ maximum de la distance entre un ordre total et $v$ tournois définis sur un ensemble à $n$ éléments ; on donne sa valeur exacte pour $v$ pair, un encadrement pour $v$ impair, et sa valeur limite pour $v$ tendant vers l’infini.

The Turán number of a given graph $H$, denoted by $\mathrm{ex}(n,H)$, is the maximum number of edges in an $H$-free graph on $n$ vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number $\text{ex}(n,K_p\cup K_q$) of a vertex-disjoint union of cliques $K_p$ and $K_q$ for all values of $n$.

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V=v₀,v₁,...,v_{n-1}$, $E₁=v₀v₁,...,v₀v_{n-3},v_{n-4}{v}_{n-2},v_{n-3}{v}_{n-1}$ and $E₂=v₀v₁,...,v₀v_{n-3},v_{n-3}{v}_{n-2},v_{n-3}{v}_{n-1}$. For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r(Tₘ,T{ₙ}^i)$, where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

A graph $G$ is called an $S$-graph if its periphery $Peri\left(G\right)$ is equal to its center eccentric vertices $Cep\left(G\right)$. Further, a graph $G$ is called a $D$-graph if $Peri\left(G\right)\cap Cep\left(G\right)=\varnothing$. We describe $S$-graphs and $D$-graphs for small radius. Then, for a given graph $H$ and natural numbers $r\ge 2$, $n\ge 2$, we construct an $S$-graph of radius $r$ having $n$ central vertices and containing $H$ as an induced subgraph. We prove an analogous existence theorem for $D$-graphs, too. At the end, we give some properties of $S$-graphs and $D$-graphs.

Let $G=\left(V\right(G),E(G\left)\right)$ be a graph. Gould and Hynds (1999) showed a well-known characterization of $G$ by its line graph $L\left(G\right)$ that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph $G$ to have a 2-factor in its line graph $L\left(G\right).$ A graph $G$ is called $N^2$-locally connected if for every vertex $x\in V\left(G\right),$$G[...$