The search session has expired. Please query the service again.
Displaying 61 –
80 of
117
We have been investigating the cryptographical properties of
in nite families of simple graphs of large girth with the special colouring
of vertices during the last 10 years. Such families can be used for the
development of cryptographical algorithms (on symmetric or public key
modes) and turbocodes in error correction theory. Only few families of
simple graphs of large unbounded girth and arbitrarily large degree are
known.
The paper is devoted to the more general theory of directed graphs of
large...
In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum. Vol. 7 (2O02) no. 26. 1280-1294]. The adjaceni eccentric distance sum index of the graph G is defined as [...] where ε(υ) is the eccentricity of the vertex υ, deg(υ) is the degree of the vertex υ and D(υ) = ∑u∊v(G) d (u,υ)is the sum...
For a bipartite graph and a non-zero real , we give bounds for the sum of the th powers of the Laplacian eigenvalues of using the sum of the squares of degrees, from which lower and upper bounds for the incidence energy, and lower bounds for the Kirchhoff index and the Laplacian Estrada index are deduced.
The reverse Wiener index of a connected graph is defined as
where is the number of vertices, is the diameter, and is the Wiener index (the sum of distances between all unordered pairs of vertices) of . We determine the -vertex non-starlike trees with the first four largest reverse Wiener indices for , and the -vertex non-starlike non-caterpillar trees with the first four largest reverse Wiener indices for .
We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...
The reaping number of a Boolean algebra is defined as the minimum size of a subset such that for each -partition of unity, some member of meets less than elements of . We show that for each , as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every -branching tree whose maximal nodes are coloured with colours contains an -branching subtree using at most colours if and only if .
Currently displaying 61 –
80 of
117