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 14 Next

Displaying 261 – 280 of 398

Showing per page

On the Stack-Size of General Tries

Jérémie Bourdon, Markus Nebel, Brigitte Vallée (2010)

RAIRO - Theoretical Informatics and Applications

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural...

On the tree structure of the power digraphs modulo n

Amplify Sawkmie, Madan Mohan Singh (2015)

Czechoslovak Mathematical Journal

For any two positive integers n and k ≥ 2 , let G ( n , k ) be a digraph whose set of vertices is { 0 , 1 , ... , n - 1 } and such that there is a directed edge from a vertex a to a vertex b if a k ≡ b ( mod n ) . Let n = ∏ i = 1 r p i e i be the prime factorization of n . Let P be the set of all primes dividing n and let P 1 , P 2 ⊆ P be such that P 1 ∪ P 2 = P and P 1 ∩ P 2 = ∅ . A fundamental constituent of G ( n , k ) , denoted by G P 2 * ( n , k ) , is a subdigraph of G ( n , k ) induced on the set of vertices which are multiples of ∏ p i ∈ P 2 p i and are relatively prime to all primes q ∈ P 1 . L. Somer and M. Křížek proved that the trees attached to all cycle...

On the Vertex Separation of Cactus Graphs

Markov, Minko (2007)

Serdica Journal of Computing

This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.

On transitive orientations of G-ê

Michael Andresen (2009)

Discussiones Mathematicae Graph Theory

A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.

On-line 𝓟-coloring of graphs

Piotr Borowiecki (2006)

Discussiones Mathematicae Graph Theory

For a given induced hereditary property 𝓟, a 𝓟-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property 𝓟. We consider the effectiveness of on-line 𝓟-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line 𝓟-coloring algorithm. In the class of generalized...

Onq-Power Cycles in Cubic Graphs

Julien Bensmail (2017)

Discussiones Mathematicae Graph Theory

In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8 only.

Ordered vertex partitioning.

McConnell, Ross M., Spinrad, Jeremy P. (2000)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

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

Currently displaying 261 – 280 of 398