The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number $χ_D(G)$ of G. Extending these concepts to infinite graphs we prove that $D(Q_ℵ₀) = 2$ and $χ_D(Q_ℵ₀) = 3$, where $Q_ℵ₀$ denotes the hypercube of countable dimension. We also show that $χ_D(Q₄) = 4$, thereby completing the investigation of finite hypercubes with respect to $χ_D$. Our results extend work on finite graphs by Bogstad and Cowen on the distinguishing number and Choi, Hartke and Kaul on the distinguishing chromatic number.
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 thinness conditions and thus significantly extend the class of graphs for which the prime factorization can be found in polynomial time.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.