Degree-constrained edge partitioning in graphs arising from discrete tomography.
Dense Arbitrarily Partitionable Graphs
A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 edges is AP or belongs to few classes of exceptional graphs.
Direct product decompositions of -digraphs
Discrete Dirac operators on Riemann surfaces and Kasteleyn matrices
Let be a flat surface of genus with cone type singularities. Given a bipartite graph isoradially embedded in , we define discrete analogs of the Dirac operators on . These discrete objects are then shown to converge to the continuous ones, in some appropriate sense. Finally, we obtain necessary and sufficient conditions on the pair for these discrete Dirac operators to be Kasteleyn matrices of the graph . As a consequence, if these conditions are met, the partition function of the dimer...
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.
Disjoint Homotopic Paths and Trees in a Planar Graph.
Disjoint triangles and quadrilaterals in a graph
Let n, s and t be three integers with s ≥ 1, t ≥ 0 and n = 3s + 4t. Let G be a graph of order n such that the minimum degree of G is at least (n + s)/2. Then G contains a 2-factor with s + t components such that s of them are triangles and t of them are quadrilaterals.
Distance independence in graphs
For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number is the maximum cardinality of a D-independent set. In particular, the independence number . Along with general results we consider, in particular, the odd-independence number where ODD = 1,3,5,....
Domatic number and degrees of vertices of a graph
Domatic numbers of cube graphs
Domination, Eternal Domination, and Clique Covering
Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and...
Domination in cubes
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...
Domination, independence and irredundance in graphs [Book]
Domination Subdivision Numbers
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that for any graph G. We give a counterexample to this conjecture. On the other hand, we show...
Double coverings and reflexive abelian hypermaps.
Ear decompositions in combed graphs.
Edge Dominating Sets and Vertex Covers
Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.
Edge-disjoint 1-factors in powers of connected graphs
Edge-domatic number of a graph