# Vol. 17 no. 3

### 1. Traceability of locally hamiltonian and locally traceable graphs

If $\mathcal{P}$ is a given graph property, we say that a graph $G$ is <i>locally</i> $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and […]
Section: Graph Theory

### 2. The inapproximability for the $(0,1)$-additive number

An <i>additive labeling</i> of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of […]
Section: Graph Theory

### 3. The irregularity of two types of trees

The irregularity of a graph $G$ is defined as the sum of weights $|d(u)-d(v)|$ of all edges $uv$ of $G$, where $d(u)$ and $d(v)$ are the degrees of the vertices $u$ and $v$ in $G$, respectively. In this paper, some structural properties on trees with maximum (or minimum) irregularity among trees […]
Section: Graph Theory

### 4. Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable

For planar graphs, we consider the problems of <i>list edge coloring</i> and <i>list total coloring</i>. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the […]
Section: Graph Theory

### 5. Edge Disjoint Hamilton Cycles in Knödel Graphs

The vertices of the Knödel graph $W_{\Delta, n}$ on $n \geq 2$ vertices, $n$ even, and of maximum degree $\Delta, 1 \leq \Delta \leq \lfloor log_2(n) \rfloor$, are the pairs $(i,j)$ with $i=1,2$ and $0 \leq j \leq \frac{n}{2} -1$. For $0 \leq j \leq \frac{n}{2} -1$, there is an edge between vertex […]
Section: Graph Theory

### 6. On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance

Assume that $n, \delta ,k$ are integers with $0 \leq k < \delta < n$. Given a graph $G=(V,E)$ with $|V|=n$. The symbol $G-F, F \subseteq V$, denotes the graph with $V(G-F)=V-F$, and $E(G-F)$ obtained by $E$ after deleting the edges with at least one endvertex in $F$. $G$ is called […]
Section: Graph Theory

### 7. Arithmetic completely regular codes

In this paper, we explore completely regular codes in the Hamming graphs and related graphs. Experimental evidence suggests that many completely regular codes have the property that the eigenvalues of the code are in arithmetic progression. In order to better understand these "arithmetic […]
Section: PRIMA 2013

### 8. Connected Tropical Subgraphs in Vertex-Colored Graphs

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the graph. In this work we study the problem of finding a minimal connected tropical subgraph. We first show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when […]
Section: Graph Theory

### 9. An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size

A graph $G$ is a $2$<i>-tree</i> if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a […]
Section: Graph Theory

### 10. Rainbow eulerian multidigraphs and the product of cycles

An arc colored eulerian multidigraph with $l$ colors is rainbow eulerian if there is an eulerian circuit in which a sequence of $l$ colors repeats. The digraph product that refers the title was introduced by Figueroa-Centeno et al. as follows: let $D$ be a digraph and let $\Gamma$ be a family of […]
Section: Graph Theory

### 11. Edge-partitioning graphs into regular and locally irregular components

A graph is locally irregular if every two adjacent vertices have distinct degrees. Recently, Baudon et al. introduced the notion of decomposition into locally irregular subgraphs. They conjectured that for almost every graph $G$, there exists a minimum integer $\chi^{\prime}_{\mathrm{irr}}(G)$ such […]
Section: Graph Theory

### 12. A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups

Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational theory […]
Section: Combinatorics

### 13. Statistics for 3-letter patterns with repetitions in compositions

A composition $\pi = \pi_1 \pi_2 \cdots \pi_m$ of a positive integer $n$ is an ordered collection of one or more positive integers whose sum is $n$. The number of summands, namely $m$, is called the number of parts of $\pi$. Using linear algebra, we determine formulas for generating functions that […]
Section: Combinatorics

### 14. Dendriform structures for restriction-deletion and restriction-contraction matroid Hopf algebras

We endow the set of isomorphism classes of matroids with a new Hopf algebra structure, in which the coproduct is implemented via the combinatorial operations of restriction and deletion. We also initiate the investigation of dendriform coalgebra structures on matroids and introduce a monomial […]
Section: Combinatorics

### 15. Avoiding patterns in irreducible permutations

We explore the classical pattern avoidance question in the case of irreducible permutations, <i>i.e.</i>, those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and […]
Section: Combinatorics

### 16. On the complexity of edge-colored subgraph partitioning problems in network optimization

Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization […]
Section: Discrete Algorithms

### 17. Energy-optimal algorithms for computing aggregative functions in random networks

We investigate a family of algorithms minimizing energetic effort in random networks computing aggregative functions. In contrast to previously considered models, our results minimize maximal energetic effort over all stations instead of the average usage of energy. Such approach seems to be much […]
Section: Discrete Algorithms

### 18. The complexity of deciding whether a graph admits an orientation with fixed weak diameter

An oriented graph $øverrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $øverrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length […]
Section: Graph Theory

### 19. Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

Let $G$ be a graph and $\mathcal{S}$ be a subset of $Z$. A vertex-coloring $\mathcal{S}$-edge-weighting of $G$ is an assignment of weights by the elements of $\mathcal{S}$ to each edge of $G$ so that adjacent vertices have different sums of incident edges weights. It was proved that every […]
Section: Graph Theory

### 20. Robust Wireless Sensor Network Deployment

In this work we present a decentralized deployment algorithm for wireless mobile sensor networks focused on deployment Efficiency, connectivity Maintenance and network Reparation (EMR). We assume that a group of mobile sensors is placed in the area of interest to be covered, without any prior […]
Section: Distributed Computing and Networking

### 21. Permutations of context-free, ET0L and indexed languages

For a language $L$, we consider its cyclic closure, and more generally the language $C^{k}(L)$, which consists of all words obtained by partitioning words from $L$ into $k$ factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators $C^k$. This […]
Section: Automata, Logic and Semantics

### 22. Linear recognition of generalized Fibonacci cubes $Q_h(111)$

The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings \$b_1b_2 \ldots […]
Section: Graph Theory