 |
Discrete Mathematics & Theoretical Computer Science |
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 Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. <b>Question 1</b> Is 9 the smallest order of a connected nontraceable locally traceable graph? <b>Question 2</b> Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.
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 $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\ell (G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(0,1)$-<i>additive labeling</i> of a graph $G$ is a function $\ell :V(G) \rightarrow \{0,1 \}$, 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)$. A graph may lack any $(0,1)$-additive labeling. We show that it is NP-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $\sigma_1 (G) = […]
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 with given degree sequence and trees with given branching number are explored, respectively. Moreover, the corresponding trees with maximum (or minimum) irregularity are also found, respectively.
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 edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.
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 $(1,j)$ and every vertex $(2,j + 2^k - 1 (mod \frac{n}{2}))$, for $k=0,1,2, \ldots , \Delta -1$. Existence of a Hamilton cycle decomposition of $W_{k, 2k}, k \geq 6$ is not yet known, see Discrete Appl. Math. 137 (2004) 173-195. In this paper, it is shown that the $k$-regular Knödel graph $W_{k,2k}, k \geq 6$ has $ \lfloor \frac{k}{2} \rfloor - 1$ edge disjoint Hamilton cycles.
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 <i>$k$-vertex fault traceable</i>, <i>$k$-vertex fault Hamiltonian</i>, or <i>$k$-vertex fault Hamiltonian-connected</i> if $G-F$ remains traceable, Hamiltonian, and Hamiltonian-connected for all $F$ with $0 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ to be $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, and $k$-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the $k$-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for $h_i(n, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.
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 completely regular codes", we focus on cartesian products of completely regular codes and products of their corresponding coset graphs in the additive case. Employing earlier results, we are then able to prove a theorem which nearly classifies these codes in the case where the graph admits a completely regular partition into such codes (e.g, the cosets of some additive completely regular code). Connections to the theory of distance-regular graphs are explored and several open questions are posed.
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 the number of colors is logarithmic in terms of the order of the graph (i.e. FPT). We then provide upper bounds for the order of the minimal connected tropical subgraph under various conditions. We finally study the problem of finding a connected tropical subgraph in a randomly vertex-colored random graph.
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 <i>graphic sequence</i> if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.
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 digraphs such that $V(F)=V$ for every $F\in \Gamma$. Consider any function $h:E(D) \longrightarrow \Gamma$. Then the product $D \otimes_h \Gamma$ is the digraph with vertex set $V(D) \times V$ and $((a,x),(b,y)) \in E(D \otimes_h \Gamma)$ if and only if $(a,b) \in E(D)$ and $(x,y) \in E(h (a,b))$. In this paper we use rainbow eulerian multidigraphs and permutations as a way to characterize the $\otimes_h$-product of oriented cycles. We study the behavior of the $\otimes_h$-product when applied to digraphs with unicyclic components. The results obtained allow us to get edge-magic labelings of graphs formed by the union of unicyclic components and with different magic sums.
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 that $G$ admits an edge-partition into $\chi^{\prime}_{\mathrm{irr}}(G)$ classes, each of which induces a locally irregular graph. In particular, they conjectured that $\chi^{\prime}_{\mathrm{irr}}(G) \leq 3$ for every $G$, unless $G$ belongs to a well-characterized family of non-decomposable graphs. This conjecture is far from being settled, as notably (1) no constant upper bound on$\chi^{\prime}_{\mathrm{irr}}(G)$ is known for $G$ bipartite, and (2) no satisfactory general upper bound on $\chi^{\prime}_{\mathrm{irr}}(G)$ is known. We herein investigate the consequences on this question of allowing a decomposition to include regular components as well. As a main result, we prove that every bipartite graph admits such a decomposition into at most $6$ subgraphs. This result implies that every graph $G$ admits a decomposition into at most $6(\lfloor \mathrm{log} \chi (G) \rfloor +1)$ subgraphs whose components are regular or locally irregular.
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 of the class of all finite epigroups and is decidable. We show that the theory is not finitely based but provide a transparent infinite basis for it.
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 count compositions of $n$ with $m$ parts, according to the number of occurrences of the subword pattern $\tau$, and according to the sum, over all occurrences of $\tau$, of the first integers in their respective occurrences, where $\tau$ is any pattern of length three with exactly 2 distinct letters.
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 invariant which satisfy a convolution identity with respect to restriction and deletion.
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 several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.
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 over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, a subgraph $H$ is said to be <i>monochromatic</i> if all its edges have the same color, and called <i>multicolored</i> if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation […]
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 more suitable for some kinds of networks, in particular ad hoc radio networks, wherein we need all stations functioning and replacing batteries after the deployment is not feasible. We analyze also the latency of proposed energy-optimal algorithms. We model a network by placing randomly and independently $n$ points in a $d$-dimensional cube of side-length $n^{1/d}$. We place an edge between vertices that interact with each other. We analyze properties of the resulting graphs in order to obtain estimates on energetic effort and latency of proposed algorithms.
Section:
Discrete Algorithms
18. The complexity of deciding whether a graph admits an orientation with fixed weak diameter
An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{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 at most $k$, we call $\overrightarrow{G}$ $k$-weak (resp. $k$-strong). We consider several problems asking whether an undirected graph $G$ admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether $G$ admits a $k$-weak orientation is NP-complete for every $k \geq 2$. This notably implies the NP-completeness of several problems asking whether $G$ is an extremal graph (in terms of needed colours) for some vertex-colouring problems.
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 3-connected bipartite graph admits a vertex-coloring $\mathcal{S}$-edge-weighting for $\mathcal{S} = \{1,2 \}$ (H. Lu, Q. Yu and C. Zhang, Vertex-coloring 2-edge-weighting of graphs, European J. Combin., 32 (2011), 22-27). In this paper, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring $\mathcal{S}$-edge-weighting for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$. These bounds we obtain are tight, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring $\mathcal{S}$-edge-weightings for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$.
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 knowledge of the environment. The goal of the algorithm is to maximize the covered area and cope with sudden sensor failures. By relying on the locally available information regarding the environment and neighborhood, and without the need for any kind of synchronization in the network, each sensor iteratively chooses the next-step movement location so as to form a hexagonal lattice grid. Relying on the graph of wireless mobile sensors, we are able to provide the properties regarding the quality of coverage, the connectivity of the graph and the termination of the algorithm. We run extensive simulations to provide compactness properties of the deployment and evaluate the robustness against sensor failures. We show through the analysis and the simulations that EMR algorithm is robust to node failures and can restore the lattice grid. We also show that even after a failure, EMR algorithm call still provide a compact deployment in a reasonable time.
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 both sharpens and generalises Brandstädt's result that if $L$ is context-free then $C^{k}(L)$ is context-sensitive and not context-free in general for $k \geq 3$. We also show that the cyclic closure of an indexed language is indexed.
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 b_h$ containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.
Section:
Graph Theory