For a nontrivial connected graph , the -degree of a vertex in a graph is the number of copies of in containing . A graph is -continuous (or -degree continuous) if the -degrees of every two adjacent vertices of differ by at most 1. All -continuous graphs are determined. It is observed that if is a nontrivial connected graph that is -continuous for all nontrivial connected graphs , then either is regular or is a path. In the case of a 2-connected graph , however, there...
En dos artículos, publicados en 1989, Balas y Ng dan una metodología para construir facetas del politopo de recubrimiento con coeficientes en {0, 1, 2}. Siguiendo esta metodología, en el presente artículo decimos cómo se contruyen facetas de dicho politopo con coeficientes en {0, 1, 2, 3}.
The class of DCT-graphs is a common generalization of the classes of almost claw-free and quasi claw-free graphs. We prove that every even (2p+1)-connected DCT-graph G is p-extendable, i.e., every set of p independent edges of G is contained in a perfect matching of G. This result is obtained as a corollary of a stronger result concerning factor-criticality of DCT-graphs.
By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the...
In this paper we present factorization theorems for strong maps between matroids of arbitrary cardinality. Moreover, we present a new way to prove the factorization theorem for strong maps between finite matroids.
A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs ₁,₂,...,ₙ a vertex (₁, ₂, ...,ₙ)-partition of a graph G is a partition V₁,V₂,...,Vₙ of V(G) such that for each i = 1,2,...,n the induced subgraph has property . The class of all graphs having a vertex (₁, ₂, ...,ₙ)-partition is denoted by ₁∘₂∘...∘ₙ. A property is said to be reducible with respect to a lattice of properties of graphs if there are n ≥ 2 properties ₁,₂,...,ₙ ∈ such that = ₁∘₂∘...∘ₙ;...
In parliaments elected by proportional systems the seats are allocated to the elected political parties roughly proportionally to the shares of votes for the party lists. Assuming that members of the parliament representing the same party are voting together, it has sense to require that distribution of the influence of the parties in parliamentary decision making is proportional to the distribution of seats. There exist measures (so called voting power indices) reflecting an ability of each party...
A fall coloring of a graph G is a proper coloring of the vertex set of G such that every vertex of G is a color dominating vertex in G (that is, it has at least one neighbor in each of the other color classes). The fall coloring number of G is the minimum size of a fall color partition of G (when it exists). Trivially, for any graph G, . In this paper, we show the existence of an infinite family of graphs G with prescribed values for χ(G) and . We also obtain the smallest non-fall colorable...
We give several characterisations of strongly projective graphs which generalise in many respects odd cycles and complete graphs [7]. We prove that all known families of projective graphs contain only strongly projective graphs, including complete graphs, odd cycles, Kneser graphs and non-bipartite distance-transitive graphs of diameter d ≥ 3.