Vol. 17 no. 3

1. Traceability of locally hamiltonian and locally traceable graphs

De Wet, Johan ; Van Aardt, Susan.
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

Ahadi, Arash ; Dehghan, Ali.
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

Jianxi, Li ; Liu, Yang ; Shiu, Wai.
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

Bonamy, Marthe ; Lévêque, Benjamin ; Pinlou, Alexandre.
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

Paulraja, Palanivel Subramania Nadar ; Sampath Kumar, S.
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

Chen, Shih-Yan ; Kao, Shin-Shin ; Su, Hsun.
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

Koolen, Jacobus ; Sun Lee, Woo ; Martin, William ; Tanaka, Hajime.
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

Anglès d'Auriac, Jean-Alexandre ; Cohen, Nathann ; El Mafthoui, Hakim ; Harutyunyan, Ararat ; Legay, Sylvain ; Manoussakis, Yannis.
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

Zeng, De-Yan ; Yin, Jian-Hua.
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

López, Susana ; Muntaner-Batle, Francesc-Antoni.
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

Bensmail, Julien ; Stevens, Brett.
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

Mikhaylova, Inna.
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

Shabani, Armend ; Gjergji, Rexhep.
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

Hoang-Nghia, Nguyen ; Tanasa, Adrian ; Tollu, Christophe.
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

Baril, Jean-Luc.
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

Zhang, Xiaoyan ; Zhang, Zan-Bo ; Broersma, Hajo ; Wen, Xuelian.
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

Klonowski, Marek ; Sulkowska, Małgorzata.
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

Bensmail, Julien ; Duvignau, Romaric ; Kirgizov, Sergey.
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

Lu, Hongliang.
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

Erdelj, Milan ; Mitton, Nathalie ; Razafindralambo, Tahiry.
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

Brough, Tara ; Ciobanu, Laura ; Elder, Murray ; Zetzsche, Georg.
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)$

Rho, Yoomi ; Vesel, Aleksander.
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