On a Certain Type of Decompositions of Complete Graphs into Factors with Equal Diameters
The additive hereditary property of linear forests is characterized by the existence of average labellings.
A graph is a -tree if either is the complete graph on vertices, or has a vertex whose neighborhood is a clique of order and the graph obtained by removing from is also a -tree. Clearly, a -tree has at least vertices, and is a 1-tree (usual tree) if and only if it is a -connected graph and has no -minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of -trees as follows: if is a graph with at least vertices, then is a -tree if...
Let a1 , . . . , ar, be positive integers, i=1 ... r, m = ∑(ai − 1) + 1 and p = max{a1 , . . . , ar }. For a graph G the symbol G → (a1 , . . . , ar ) means that in every r-coloring of the vertices of G there exists a monochromatic ai -clique of color i for some i ∈ {1, . . . , r}. In this paper we consider the vertex Folkman numbers F (a1 , . . . , ar ; m − 1) = min |V (G)| : G → (a1 , . . . , ar ) and Km−1 ⊂ G} We prove that F (a1 , . . . , ar ; m − 1) = m + 6, if p = 3 and m ≧ 6 (Theorem 3)...
A digraph D = (V,A) is arc-traceable if for each arc xy in A, xy lies on a directed path containing all the vertices of V, i.e., hamiltonian path. We prove a conjecture of Quintas [7]: if D is arc-traceable, then the condensation of D is a directed path. We show that the converse of this conjecture is false by providing an example of an upset tournament which is not arc-traceable. We then give a characterization for upset tournaments in terms of their score sequences, characterize which arcs of...
We assign to each positive integer a digraph whose set of vertices is and for which there is a directed edge from to if . We establish necessary and sufficient conditions for the existence of isolated fixed points. We also examine when the digraph is semiregular. Moreover, we present simple conditions for the number of components and length of cycles. Two new necessary and sufficient conditions for the compositeness of Fermat numbers are also introduced.
We consider cubic graphs formed with k ≥ 2 disjoint claws (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of are joined to the three vertices of degree 1 of and joined to the three vertices of degree 1 of . Denote by the vertex of degree 3 of and by T the set . In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices induce j cycles (note that the graphs...