Decomposition of complete graphs into factors of diameter two
Decomposition tree and indecomposable coverings
Let G = (V,A) be a directed graph. With any subset X of V is associated the directed subgraph G[X] = (X,A ∩ (X×X)) of G induced by X. A subset X of V is an interval of G provided that for a,b ∈ X and x ∈ V∖X, (a,x) ∈ A if and only if (b,x) ∈ A, and similarly for (x,a) and (x,b). For example ∅, V, and {x}, where x ∈ V, are intervals of G which are the trivial intervals. A directed graph is indecomposable if all its intervals are trivial. Given an integer k > 0, a directed graph G = (V,A) is called...
Degree Sequences of Monocore Graphs
A k-monocore graph is a graph which has its minimum degree and degeneracy both equal to k. Integer sequences that can be the degree sequence of some k-monocore graph are characterized as follows. A nonincreasing sequence of integers d0, . . . , dn is the degree sequence of some k-monocore graph G, 0 ≤ k ≤ n − 1, if and only if k ≤ di ≤ min {n − 1, k + n − i} and ⨊di = 2m, where m satisfies [...] ≤ m ≤ k ・ n − [...] .
Die Minimalbasis der Menge aller nicht in die projektive Ebene einbettbaren Graphen.
Digraphs with large exponent.
Disjoint 5-cycles in a graph
We prove that if G is a graph of order 5k and the minimum degree of G is at least 3k then G contains k disjoint cycles of length 5.
Dispersed Points and Geometric Embedding of Complete Bipartite Graphs.
Distance perfectness of graphs
In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].
Dominant-matching graphs
We introduce a new hereditary class of graphs, the dominant-matching graphs, and we characterize it in terms of forbidden induced subgraphs.
Dominating bipartite subgraphs in graphs
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
Domination and independence subdivision numbers of graphs
The domination subdivision number of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of adjacent vertices...
Domination and leaf density in graphs
The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are obtained for...
Domination in partitioned graphs
Let V₁, V₂ be a partition of the vertex set in a graph G, and let denote the least number of vertices needed in G to dominate . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value...