O perfektních a kvaziperfektních grafech
O vnoření dichotomického stromu do krychle
Odd-vertex-degree trees maximizing Wiener index
On a certain ordering of the vertices of a tree
On a characterization of -trees
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...
On a matching distance between rooted phylogenetic trees
The Robinson-Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite graphs, the values...
On a problem of linear arboricity
On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k
A k-tree is a tree with maximum degree at most k. In this paper, we give a degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than k. We denote by σk(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k ≥ 3 and s ≥ 0 be integers, and suppose G is a connected graph and σk(G) ≥ |V (G)|+s−1. Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree less than k. The degree...
On acyclic colorings of direct products
A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ is mn-m-2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.
On binary representations of integers with digits .
On binary trees and permutations
Every binary tree is associated to a permutation with repetitions, which determines it uniquely. Two operations are introduced and used for the construction of the set of all binary trees. The set of all permutations which correspond to a given binary tree is determined and its cardinal number is evaluated.
On Catalan trees and the Jacobian conjecture.
On Cayley's enumeration of alkanes (or 4-valent trees).
On Cayley's formula for counting trees in nested interval graphs.
On Closed Modular Colorings of Trees
Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood...
On computing the distinguishing numbers of trees and forests.
On cubes and dichotomic trees
On Decomposing Regular Graphs Into Isomorphic Double-Stars
A double-star is a tree with exactly two vertices of degree greater than 1. If T is a double-star where the two vertices of degree greater than one have degrees k1+1 and k2+1, then T is denoted by Sk1,k2 . In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star Sk,k−1 decomposes every 2k-regular graph that contains a perfect matching.
On distances and metrics in discrete ordered sets
Discrete partially ordered sets can be turned into distance spaces in several ways. The distance functions may or may not satisfy the triangle inequality and restrictions of the distance to finite chains may or may not coincide with the natural, difference-of-height distance measured in a chain. It is shown that for semilattices the semimodularity ensures the good behaviour of the distances considered. The Jordan-Dedekind chain condition, which is weaker than semimodularity, is equivalent to the...
On distances between isomorphism classes of graphs
In 1986, Chartrand, Saba and Zou [3] defined a measure of the distance between (the isomorphism classes of) two graphs based on 'edge rotations'. Here, that measure and two related measures are explored. Various bounds, exact values for classes of graphs and relationships are proved, and the three measures are shown to be intimately linked to 'slowly-changing' parameters.