The He matrix, put forward by He and He in 1989, is designed as a means for uniquely representing the structure of a hexagonal system (= benzenoid graph). Observing that the He matrix is just the adjacency matrix of a pertinently weighted inner dual of the respective hexagonal system, we establish a number of its spectral properties. Afterwards, we discuss the number of eigenvalues equal to zero of the He matrix of a hexagonal system. Moreover, we obtain a relation between the number of triangles...

Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...

This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For...

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 assumptions...

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

For any two positive integers $n$ and $k\ge 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\equiv b(modn)$. Let $n={\prod }_{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\subseteq P$ be such that $P_1\cup P_2=P$ and $P_1\cap P_2=\varnothing$. 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 ${\prod }_{p_i\in P_2}{p}_i$ and are relatively prime to all primes $q\in P_1$. L. Somer and M. Křížek proved that the trees attached to all cycle...

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.

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.

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

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.