All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 188

Showing per page

Pancyclism and small cycles in graphs

Ralph Faudree, Odile Favaron, Evelyne Flandrin, Hao Li (1996)

Discussiones Mathematicae Graph Theory

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), d C ( u , v ) being the distance of u and v on a hamiltonian cycle of G.

Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search

E. N. Cáceres, S. W. Song, J. L. Szwarcfiter (2010)

RAIRO - Theoretical Informatics and Applications

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of...

Parity vertex colorings of binomial trees

Petr Gregor, Riste Škrekovski (2012)

Discussiones Mathematicae Graph Theory

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.

Parity vertex colouring of graphs

Piotr Borowiecki, Kristína Budajová, Stanislav Jendrol', Stanislav Krajci (2011)

Discussiones Mathematicae Graph Theory

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),...

Partial covers of graphs

Jirí Fiala, Jan Kratochvíl (2002)

Discussiones Mathematicae Graph Theory

Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...

Partial sum of eigenvalues of random graphs

Israel Rocha (2020)

Applications of Mathematics

Let G be a graph on n vertices and let λ 1 ≥ λ 2 ≥ ... ≥ λ n be the eigenvalues of its adjacency matrix. For random graphs we investigate the sum of eigenvalues s k = ∑ i = 1 k λ i , for 1 ≤ k ≤ n , and show that a typical graph has s k ≤ ( e ( G ) + k 2 ) / ( 0 . 99 n ) 1 / 2 , where e ( G ) is the number of edges of G . We also show bounds for the sum of eigenvalues within a given range in terms of the number of edges. The approach for the proofs was first used in Rocha (2020) to bound the partial sum of eigenvalues of the Laplacian matrix.

Currently displaying 21 – 40 of 188