Tight upper bounds for the domination numbers of graphs with given order and minimum degree.
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 maximum de la distance entre un ordre total et tournois définis sur un ensemble à éléments ; on donne sa valeur exacte pour pair, un encadrement pour impair, et sa valeur limite pour tendant vers l’infini.
The Turán number of a given graph , denoted by , is the maximum number of edges in an -free graph on vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number ) of a vertex-disjoint union of cliques and for all values of .
Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with , and . 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 , where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.
A graph is called an -graph if its periphery is equal to its center eccentric vertices . Further, a graph is called a -graph if . We describe -graphs and -graphs for small radius. Then, for a given graph and natural numbers , , we construct an -graph of radius having central vertices and containing as an induced subgraph. We prove an analogous existence theorem for -graphs, too. At the end, we give some properties of -graphs and -graphs.
Let be a graph. Gould and Hynds (1999) showed a well-known characterization of by its line graph that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph to have a 2-factor in its line graph A graph is called -locally connected if for every vertex