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.
It is a known result that if a finite abelian group of odd order is a direct product of lacunary cyclic subsets, then at least one of the factors must be a subgroup. The paper gives an elementary proof that does not rely on characters.
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...