If n, t are natural numbers, μ is an infinite cardinal, G is an n-chromatic graph of cardinality at most μ, then there is a graph X with , |X| = μ⁺, such that every subgraph of X of cardinality < t is n-colorable.
Let k and ℓ be positive integers with ℓ ≤ k − 2. It is proved that there exists a positive integer c depending on k and ℓ such that every graph of order (2k−1−ℓ/k)n+c contains n vertex disjoint induced subgraphs, where these subgraphs are isomorphic to each other and they are isomorphic to one of four graphs: (1) a clique of order k, (2) an independent set of order k, (3) the join of a clique of order ℓ and an independent set of order k − ℓ, or (4) the union of an independent set of order ℓ and...
A graph is said to be reconstructible if it is determined up to isomor- phism from the collection of all its one-vertex deleted unlabeled subgraphs. Reconstruction Conjecture (RC) asserts that all graphs on at least three vertices are reconstructible. In this paper, we prove that interval-regular graphs and some new classes of graphs are reconstructible and show that RC is true if and only if all non-geodetic and non-interval-regular blocks G with diam(G) = 2 or diam(Ḡ) = diam(G) = 3 are reconstructible...
Let be a tree, let be its vertex. The branch weight of is the maximum number of vertices of a branch of at . The set of vertices of in which attains its minimum is the branch weight centroid of . For finite trees the present author proved that coincides with the median of , therefore it consists of one vertex or of two adjacent vertices. In this paper we show that for infinite countable trees the situation is quite different.
A theorem is proved which implies affirmative answers to the problems of E. Prisner. One problem is whether there are cycles of the line graph operator with period other than 1, the other whether there are cycles of the 4-edge graph operator with period greater than 2. Then a similar theorem follows.