Decompositions of graphs into 5-cycles and other small graphs.
Decompositions of multigraphs into parts with the same size
Given a family ℱ of multigraphs without isolated vertices, a multigraph M is called ℱ-decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of ℱ. We present necessary and sufficient conditions for existence of such decompositions if ℱ consists of all multigraphs of size q except for one. Namely, for a multigraph H of size q we find each multigraph M of size kq, such that every partition of the edge set of M into parts of cardinality q contains a part...
Decompositions of multigraphs into parts with two edges
Given a family 𝓕 of multigraphs without isolated vertices, a multigraph M is called 𝓕-decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of 𝓕. We present necessary and sufficient conditions for the existence of such decompositions if 𝓕 comprises two multigraphs from the set consisting of a 2-cycle, a 2-matching and a path with two edges.
Decompositions of nearly complete digraphs into t isomorphic parts
An arc decomposition of the complete digraph Kₙ into t isomorphic subdigraphs is generalized to the case where the numerical divisibility condition is not satisfied. Two sets of nearly tth parts are constructively proved to be nonempty. These are the floor tth class ( Kₙ-R)/t and the ceiling tth class ( Kₙ+S)/t, where R and S comprise (possibly copies of) arcs whose number is the smallest possible. The existence of cyclically 1-generated decompositions of Kₙ into cycles and into paths is characterized....
Decompositions of Plane Graphs Under Parity Constrains Given by Faces
An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial (facially proper)...
Decompositions of quadrangle-free planar graphs
W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.
Deducing Properties of Trees From Their Matula Numbers
Defective choosability of graphs in surfaces
It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic ε, and k and d are positive integers such that k ≥ 3 and d is sufficiently large in terms of k and ε, then G is (k,d)*-colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved for list colorings...
Defective choosability of graphs without small minors.
Definability in structures of finite valency
Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph
In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c). The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G = Cₘ × Kₙ, c)...
Definizione dei clan binari e loro classificazione
L’albero binario (libero) è una struttura analoga a quella dei numeri naturali (standard), salvo che ci sono due operazioni di successivo. Nello studio degli alberi binari non standard, si ha bisogno di strutture ordinate che stiano a quella di albero binario libero come la struttura (ordinata) Z sta ad N. Si introducono perciò i clan binari e se ne studiano le classi di isomorfismo. Si dimostra che esse sono determinate dalle classi di similitudine delle successioni numerabili di 2 elementi, avendo...
Deformation and rigidity of simplicial group actions on trees.
Degree constrained orientations in countable graphs.
Degree distribution nearby the origin of a preferential attachment graph.
Degree distributions in general random intersection graphs.
Degree Equitable Domination on Graphs
Degree polynomial for vertices in a graph and its behavior under graph operations
We introduce a new concept namely the degree polynomial for the vertices of a simple graph. This notion leads to a concept, namely, the degree polynomial sequence which is stronger than the concept of degree sequence. After obtaining the degree polynomial sequence for some well-known graphs, we prove a theorem which gives a necessary condition for the realizability of a sequence of polynomials with positive integer coefficients. Also we calculate the degree polynomial for the vertices of the join,...
Degree powers in graphs with a forbidden even cycle.
Degree powers in graphs with forbidden subgraphs.