On List Coloring with Separation of the Complete Graph and Set System Intersections

We consider the following list coloring with separation problem: Given a graph $G$ and integers $a,b$, find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|= a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $\varphi$ of sets of integers to the vertices of $G$ such that $\varphi(u)\subset L(u)$ and $|\varphi(v)|=b$ for any vertex $u$ and $\varphi(u)\cap \varphi(v)=\emptyset$ for any edge $uv$. Such a value of $c$ is called the separation number of $(G,a,b)$. Using a special partition of a set of lists for which we obtain an improved version of Poincar\'e's crible, we determine the separation number of the c…

Fuzzy Logic based model for self-optimizing energy consumption in IoT environment

Energy optimization is essential in IoT environments due to energy constraints for some IoT components. In fact, energy consumption has a direct impact on IoT system lifetime, which represents an important Quality of Service (QoS) parameter for IoT environments. In order to extend the IoT system lifetime, energy consumption optimization should be considered in several IoT components. In this paper, we specify an energy self-optimizing mechanism allowing to minimize data transmission energy consumption of IoT objects. This mechanism enables selecting specific objects to send the desired data while minimizing the energy consumed for the corresponding communication. Our proposal is made of a M…

On the family of $r$-regular graphs with Grundy number $r+1$

International audience; The Grundy number of a graph $G$, denoted by $\Gamma(G)$, is the largest $k$ such that there exists a partition of $V(G)$, into $k$ independent sets $V_1,\ldots, V_k$ and every vertex of $V_i$ is adjacent to at least one vertex in $V_j$, for every $j < i$. The objects which are studied in this article are families of $r$-regular graphs such that $\Gamma(G) = r + 1$. Using the notion of independent module, a characterization of this family is given for $r=3$. Moreover, we determine classes of graphs in this family, in particular the class of $r$-regular graphs without induced $C_4$, for $r \le 4$. Furthermore, our propositions imply results on partial Grundy number.

Almost disjoint spanning trees

International audience; In this extended abstract, we only consider connected graphs. Let k ≥ 2 be an integer and T 1 ,. .. , T k be spanning trees in a graph G. A vertex is said to be an inner vertex in a tree T if it has degree at least 2 in T. We denote by I(T) the set of inner vertices of tree T. The spanning trees T 1 ,. .. , T k are completely independent spanning trees if any vertex from G is an inner vertex in at most one tree among T 1 ,. .. , T k and the trees T 1 ,. .. , T k are pairwise edge-disjoint. Completely independent spanning trees were introduced by Hasunuma [4] and then have been studied on different classes of graphs, such as underlying graphs of line graphs [4], maxim…

Gestion du niveau de service dans l’Internet des objets (IdO)

International audience

Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees

International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…

QBAIoT: QoS Based Access for IoT Environments

Self-establishing a Service Level Agreement within Autonomic Cloud Networking Environment

International audience; Today, cloud networking which is the ability to connect the user with his cloud services and to interconnect these services within an inter-cloud approach, is one of the recent research areas in the cloud computing research communities. The main drawback of cloud networking consists in the lack of Quality of Service (QoS) guarantee and management in conformance with a corresponding Service Level Agreement (SLA). Several research works have been proposed for the SLA establishing in cloud computing, but not in cloud networking. In this paper, we propose an architecture for self-establishing an end-to-end service level agreement between a Cloud Service User (CSU) and a …

Recherche d'arbres couvrants complètement indépendants dans des graphes réguliers

International audience; Nous étudions l'existence de $r$ arbres couvrants complètement indépendants dans des graphes $2r$-réguliers et $2r$-connexes, et énonçons des conditions nécessaires à leur existence. Nous déterminons le nombre maximum d'arbres dans les produits cartésiens d'une clique et d'un cycle. Nous montrons que ce nombre n'est pas toujours $r$.

The radio antipodal and radio numbers of the hypercube

International audience; A radio k-labeling of a connected graph G is an assignment f of non negative integers to the vertices of G such that |f(x) − f(y)| \ge k + 1 − d(x, y), for any two vertices x and y, where d(x, y) is the distance between x and y in G. The radio antipodal number is the minimum span of a radio (diam(G) − 1)-labeling of G and the radio number is the minimum span of a radio (diam(G))-labeling of G. In this paper, the radio antipodal number and the radio number of the hypercube are determined by using a generalization of binary Gray codes.

Strong chromatic index of products of graphs

Graphs and Algorithms

Total and fractional total colourings of circulant graphs

International audience; In this paper, the total chromatic number and the fractional total chromatic number of circulant graphs are studied. For cubic circulant graphs we give upper bounds on the fractional total chromatic number and for 4-regular circulant graphs we find the total chromatic number for some cases and we give the exact value of the fractional total chromatic number in most cases.

Adjacent vertex distinguishing edge-colorings of meshes and hypercubes

International audience

Construction of Disjoint Virtual Backbones for Wireless Sensor Networks

A wireless sensor network is a wireless network of sensors aimed at monitoring physical events. It has ingratiated itself into almost all areas of human endeavors. Data dissemination in these networks is quite challenging and is generally accomplished by flooding. But flooding introduces broadcast storm problem due from implosion and overlap. To overcome this, topology management can prescribe a virtual backbone network to which routing is confined. In this paper we propose an algorithm that constructs multiple disjoint virtual backbone networks, using only nodes' locations. The disjointedness makes routing more robust and the network exploitation energy efficient. Simulations show our algo…

Radio Labelings of Distance Graphs

A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.

IMRR and IMPR Routing Protocols For Inter and Intra Wireless Mesh Communications

Given the evolution of wireless technologies, Wireless Mesh Networks (WMN) have appeared as an emerging low-cost solution to ensure last-mile connectivity to the Internet network. However, providing real-time and streaming applications, such as VoIP (Voice over IP) and VoD (Video on Demand), with a satisfying QoS level is considered as an important challenge within these networks. In this paper, we propose a QoS based routing protocol, called Hybrid QoS Mesh Routing (HQMR), jointly with a clustering algorithm to improve the scalability of mesh networks. HQMR is composed of two routing sub- protocols: a reactive QoS based routing protocol for intra-mesh infrastructure communications and a pr…

Comparing Link Filtering Backbone Techniques in Real-World Networks

On Packing Colorings of Distance Graphs

International audience; The {\em packing chromatic number} $\chi_{\rho}(G)$ of a graph $G$ is the least integer $k$ for which there exists a mapping $f$ from $V(G)$ to $\{1,2,\ldots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. This paper studies the packing chromatic number of infinite distance graphs $G(\mathbb{Z},D)$, i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set, with two distinct vertices $i,j\in \mathbb{Z}$ being adjacent if and only if $|i-j|\in D$. We present lower and upper bounds for $\chi_{\rho}(G(\mathbb{Z},D))$, showing that for finite $D$, the packing chromatic number is finite. Our main result concerns distance graphs with $D=…

Self-configuring multipath intra-mesh infrastructure QoS based routing

International audience; Multi-path routing concept was largely exploited in wireless networks to provide benefits such as fault tolerance, load balancing, performance improvement in terms of latency, etc. In this paper, we propose a multi-path routing based protocol named MP-IMRR (Multi-path Intra-Mesh infrastructure Routing protocol) to improve our previously defined QoS based routing protocol for wireless mesh networks (i.e. IMRR). MP-IMRR is defined in order to achieve better reactivity and faster recovery from eventual route failures than the IMRR protocol by adopting the backup routes concept. Besides, given the complexity increase while considering network management systems, we adopt…

QoS Multi-tree Based Routing Protocol for Inter-mesh Infrastructure Communications

Part 5: Network Protocols; International audience; Quality of service (QoS) in wireless mesh networks (WMN) is an active area of research, which is driven by the increasing demand for real-time and multimedia applications, such as VoIP (Voice over IP) and VoD (Video on Demand). In this paper, we propose a QoS multi-tree based routing protocol for wireless mesh environments, named Inter-Mesh Infrastructure Proactive Routing (IMPR). It is a proactive multi-tree routing protocol enabling QoS guarantee for communications from/towards the Internet network through the Mesh Gateway (MG) of the mesh infrastructure. We describe and analyze the simulation results of different scenarios conducted on t…

Hybrid QoS Based Routing for IEEE 802.16j Mesh Infrastructure

Acceptance rate: 29%; International audience; With the growth of wireless networks, Wireless Mesh Network (WMN) has appeared as an emerging key solution for broadband Internet access with a low-cost deployment. Moreover, providing QoS guarantees for real-time and streaming applications such as VoIP (Voice over IP) and VoD (Video on Demand) is a challenging issue in such environment. In this paper, we propose a hybrid wireless mesh architecture to provide mesh clients with Internet access while guaranteeing QoS. It is formed by an IEEE 802.16j based infrastructure and several IEEE 802.11s based client domains. A lustering algorithm is developed to enhance scalability issues within the mesh i…

Filtering Real World Networks: A Correlation Analysis of Statistical Backbone Techniques

Networks are an invaluable tool for representing and understanding complex systems. They offer a wide range of applications, including identifying crucial nodes, uncovering communities, and exploring network formation. However, when dealing with large networks, the computational challenge can be overwhelming. Fortunately, researchers have developed several techniques to address this issue by reducing network size while preserving its fundamental properties [1-9]. To achieve this goal, two main approaches have emerged: structural and statistical methods. Structural methods aim to keep a set of topological features of the network while reducing its size. In contrast, statistical methods elimi…

Distributed Leader Election and Computation of Local Identifiers for Programmable Matter

International audience; The context of this paper is programmable matter, which consists of a set of computational elements, called particles, in an infinite graph. The considered infinite graphs are the square, triangular and king grids. Each particle occupies one vertex, can communicate with the adjacent particles, has the same clockwise direction and knows the local positions of neighborhood particles. Under these assumptions, we describe a new leader election algorithm affecting a variable to the particles, called the k-local identifier, in such a way that particles at close distance have each a different k-local identifier. For all the presented algorithms, the particles only need a O(…

The irregularity strength of circulant graphs

AbstractThe irregularity strength of a simple graph is the smallest integer k for which there exists a weighting of the edges with positive integers at most k such that all the weighted degrees of the vertices are distinct. In this paper we study the irregularity strength of circulant graphs of degree 4. We find the exact value of the strength for a large family of circulant graphs.

Service level guarantee framework for IoT environments

Nowadays, providing IoT environments with service level guarantee is a challenging task. We propose a framework for IoT service level guarantee thanks to several specific Service Level Agreements (SLAs) for IoT environments. We specify different SLAs for each entity contributing in our IoT architecture in order to conclude a global SLA called IoT-SLA (iSLA). These different SLAs enable IoT service provision with Quality of Service (QoS) guarantee. Achieving this guarantee requires several communications and interactions between the components of the proposed IoT architecture. These interactions allow an IoT Service Provider (IoT-SP) to conclude the iSLA with an IoT Client (IoT-C). We specif…

IP-Based Mobility Management and Handover Latency Measurement in heterogeneous environments

International audience; One serious concern in the ubiquitous networks is the seamless vertical handover management between different wireless technologies. To meet this challenge, many standardization organizations proposed different protocols at different layers of the protocol stack. The Internet Engineering Task Force (IETF) has different groups working on mobility at IP level in order to enhance mobile IPv4 and mobile IPv6 with different variants: HMIPv6 (Hierarchical Mobile IPv6), FMIPv6 (Fast Mobile IPv6) and PMIPv6 (Proxy Mobile IPv6) for seamless handover. Moreover, the IEEE 802.21 standard provides another framework for seamless handover. The 3GPP standard provides the Access Netw…

Fuzzy Logic Based Security Trust Evaluation for IoT Environments

In the new technological era called the Internet of Things (IoT), people, machines and objects communicate with each other via the Internet by exchanging information. In this context, trust plays an important role and is considered as a key factor in the success of the IoT services expansion. IoT services and applications use in some cases data concerning the privacy of their users. Consequently, users should trust the entities exchanging their personal information. In this paper, we present a framework that evaluates the security trust level of IoT nodes based on a Fuzzy Logic model using different input parameters such as Device Physical Security, Device Security Level and Device Ownershi…

Subdivision into i-packings and S-packing chromatic number of some lattices

An ?$i$?-packing in a graph ?$G$? is a set of vertices at pairwise distance greater than ?$i$?. For a nondecreasing sequence of integers ?$S=(s_1,s_2,\ldots)$?, the?$S$?-packing chromatic number of a graph ?$G$? is the least integer ?$k$? such that there exists a coloring of ?$G$? into ?$k$? colors where each set of vertices colored ?$i$?, ?$i=1,\ldots,k$?, is an ?$s_i$?-packing. This paper describes various subdivisions of an ?$i$?-packing into ?$j$?-packings ?$(j>i)$? for the hexagonal, square and triangular lattices. These results allow us to bound the ?$S$?-packing chromatic number for these graphs, with more precise bounds and exact values for sequences ?$S=(s_i,i \in \mathbb{N}^*)$?, …

Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes

A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…

Towards Service Level Guarantee within IoT Sensing Layer

Resource Self-management under an SLA within a Cloud Networking Environment

International audience; Today, cloud networking is one of the recent research areas in the cloud computing research communities. The main drawback of cloud networking consists in the lack of Quality of Service (QoS) guarantee and management in conformance with a corresponding Service Level Agreement (SLA). In this paper, we propose a framework for self-establishing an end-to-end SLA between a Cloud Service User (CSU) and several Cloud Service Providers (CSPs) in a cloud networking environment (inter-cloud Broker and Federation architecture). Then, we propose the self-management of cloud resources under the established SLA using specific autonomic cloud managers. We simulate our proposed fra…

Multilevel Bandwidth and Radio Labelings of Graphs

This paper introduces a generalization of the graph bandwidth parameter: for a graph G and an integer k ≤ diam(G), the k-level bandwidth Bk(G)of G is defined by Bk(G) = minγ max{|γ(x)-γ(y)|-d(x, y)+1 : x, y ∈ V (G), d(x, y) ≤ k}, the minimum being taken among all proper numberings γ of the vertices of G. We present general bounds on Bk(G) along with more specific results for k = 2 and the exact value for k = diam(G). We also exhibit relations between the k-level bandwidth and radio k-labelings of graphs from which we derive a upper bound for the radio number of an arbitrary graph.

An empirical investigation of Backbone Filtering Techniques in weighted Complex Networks

Many real-world networks' size and density hinder visualization and graph processing. Several approaches have been developed over the years to reduce the network size while representing the original network as well as possible. "Edge-filtering" techniques focus on removing nodes and edges among the so-called backbone extraction techniques. They can be classified further into "structural" and "statistical". The structural techniques, such as the High-Salience-Skeleton, Doubly-Stochastic Transformation, and the Distance Backbone filter edges according to a criterion allowing the latent structure of the network to emerge. Statistical techniques such as the Disparity Filter, Noise Corrected, an…

Force d'irrégularité des graphes circulants

National audience

Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes

The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…

Optical Routing of Uniform Instances in Cayley Graphs

Abstract Abstract We consider the problem of routing uniform communication instances in Cayley graphs. Such instances consist of all pairs of nodes whose distance is included in a specified set U. We give bounds on the load induced by these instances on the links and for the wavelength assignment problem as well. For some classes of Cayley graphs that have special symmetry property (rotational graphs), we are able to construct routings for uniform instances such that the load is the same for each link of the graph.

Broker and Federation Based Cloud Networking Architecture for IaaS and NaaS QoS Guarantee

International audience; Today, the Cloud networking aspect is a critical factor for adopting the Cloud computing approach. The main drawback of Cloud networking consists in the lack of Quality of Service (QoS) guarantee and management in conformance with a corresponding Service Level Agreement (SLA). This paper presents a framework for resource allocation according to an end-to-end SLA established between a Cloud Service User (CSU) and several Cloud Service Providers (CSPs) in a Cloud networking environment. We focus on QoS parameters for Network as a Service (NaaS) and Infrastructure as a Service (IaaS) services. In addition, we propose algorithms for the best CSPs selection to allocate Vi…

Routage Hybride basé sur la QoS pour une infrastructure IEEE 802.16j maillé sans fil

International audience

Bounds for minimum feedback vertex sets in distance graphs and circulant graphs

Graphs and Algorithms

Statistical learning and multiple linear regression model for network selection using MIH

Award of Appreciation; International audience; A key requirement to provide seamless mobility and guaranteeing Quality of Service in heterogeneous environment is to select the best destination network during handover. In this paper, we propose a new schema for network selection based on Multiple Linear Regression Model (MLRM). A horough investigation, on a huge live data collected from GPRS/UMTS networks led to identify the Key Performance Indicators (KPIs) that play the most important role in the handover process. These KPIs are: Received Signal Code Power (RSCP), received energy per chip (Ec/No) and Available Bandwidth (ABW) of the destination network. To extract a handover model from col…

Every triangle-free induced subgraph of the triangular lattice is(5m,2m)-choosable

A graph G is (a,b)-choosable if for any color list of size a associated with each vertex, one can choose a subset of b colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer m>=1, every finite triangle-free induced subgraph of the triangular lattice is (5m,2m)-choosable.

NetBone: A Python Package for Extracting Backbones of Weighted Networks

NetBone is a new open-source Python package designed to simplify analyzing complex networks. With a wide range of techniques available, Net-Bone allows researchers to extract the backbone of a network while preserving its essential structure. The package includes nine structural methods and five statistical techniques, offering users a comprehensive solution to network analysis. It is user-friendly and straightforward to use, with easy installation. The package accepts different types of inputs, including data frames or Networkx graphs, and provides evaluation measures for comparative purposes. Additionally, NetBone offers an option to generate plots. Its versatility makes it a valuable too…

ℓ-distant Hamiltonian walks in Cartesian product graphs

Abstract We introduce and study a generalisation of Hamiltonian cycles: an l-distant Hamiltonian walk in a graph G of order n is a cyclic ordering of its vertices in which consecutive vertices are at distance l. Conditions for a Cartesian product graph to possess such an l-distant Hamiltonian walk are given and more specific results are presented concerning toroidal grids.

Completely independent spanning trees in some regular graphs

International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…

IoT-MAAC: Multiple Attribute Access Control for IoT environments

Access Control is an important security service that should be considered in IoT environments in order to offer reliable IoT services. Access control in IoT environments concerns not only the access of IoT users to IoT services and objects, but also the access of IoT objects to IoT gateways. In this paper, we specify an access control mechanism that considers the access of IoT objects to IoT gateways in order to enhance the reliability of IoT data provided by the IoT objects. Our proposed access control mechanism, called IoT-MAAC (Multi Attribute Access Control), allows retrieving requested data from the most reliable and secured IoT objects among the available objects in the IoT environmen…

QoS Based Routing Protocol for Intra-Mesh Infrastructure Communications

International audience; Mesh Networks (WMNs) have been considered as a promising alternative to conventional wired networks, thanks to its flexibility and easy deployment. Thus, to ensure a satisfying level of QoS guarantees for real-time and streaming applications such as Voice over IP (VoIP) and Video on Demand (VoD), we propose a novel QoS based routing protocol for wireless mesh environments, called Hybrid QoS Mesh Routing (HQMR), jointly with a clustering algorithm to enhance scalability issues within the mesh infrastructure. HQMR is composed of two routing sub-protocols: a reactive routing sub-protocol for intra-infrastructure communications and a proactive QoS based multi-tree routin…

Linear and cyclic radio k-labelings of trees

International audience; Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two distinct vertices x and y, where dG(x,y) is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear (cyclic, respectively) radio k-labeling number of G is the minimum span of a linear (cyclic, respectively) radio k-labeling of G. In this p…

Radio k-Labelings for Cartesian Products of Graphs

International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…

Autonomic Brokerage Service for an End-to-End Cloud Networking Service Level Agreement

8 pages; International audience; Today, cloud networking which is the ability to connect the user with his cloud services and to interconnect these services within an inter-cloud approach, is one of the recent research areas in the cloud computing research communities. The main drawback of cloud networking consists in the lack of Quality of Service (QoS) assurance and management in conformance with a corresponding Service Level Agreement (SLA). In this paper, we propose a framework for self-establishing an end-to-end service level agreement between a Cloud Service User (CSU) and multiple Cloud Service Providers (CSPs) in a cloud networking environment using brokerage service. We focus on Qo…

On parameterized complexity to determine b-chromatic and partial Grundy numbers

International audience

On the family ofr-regular graphs with Grundy numberr+1

Abstract The Grundy number of a graph G , denoted by Γ ( G ) , is the largest k such that there exists a partition of V ( G ) , into k independent sets V 1 , … , V k and every vertex of V i is adjacent to at least one vertex in V j , for every j i . The objects which are studied in this article are families of r -regular graphs such that Γ ( G ) = r + 1 . Using the notion of independent module, a characterization of this family is given for r = 3 . Moreover, we determine classes of graphs in this family, in particular, the class of r -regular graphs without induced C 4 , for r ≤ 4 . Furthermore, our propositions imply results on the partial Grundy number.

A Comparison of Model-Based Backbone Filtering Techniques in the Air Transportation Network

Leader election and local identifiers for three‐dimensional programmable matter

International audience; In this paper, we present two deterministic leader election algorithms for programmable matter on the face-centered cubic grid. The face-centered cubic grid is a 3-dimensional 12-regular infinite grid that represents an optimal way to pack spheres (i.e., spherical particles or modules in the context of the programmable matter) in the 3-dimensional space. While the first leader election algorithm requires a strong hypothesis about the initial configuration of the particles and no hypothesis on the system configurations that the particles are forming, the second one requires fewer hypothesis about the initial configuration of the particles but does not work for all pos…

Gestion de la qualité de service dans les réseaux maillés sans fil

International audience

Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs

AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.

SREP: An Energy Efficient Relay Protocol for Wireless Sensor Networks

While wireless sensor networks continue to break new grounds in applications, favored by technological innovations, energy efficiency continues to stagnate. Duty cycling remains the most popular and effective technique used to improve energy efficiency and thus lifetime of the network. Nevertheless, duty cycling imposes temporary unavailability on the network leading to deterioration of quality of service. To take care of this rather contradicting reality, this paper proposes Sleep Relay Protocol (SREP). Network nodes are divided into sets according to their location and the sets sleep in relay within a duty cycle period. Two set formation algorithms are proposed at initiation of our propos…

Packing colorings of subcubic outerplanar graphs

Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$-packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$, the distance between $x$ and $y$ is greater than $s_i$. The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$-packing coloring of a graph $G$ is called the packing chromatic number of $G$, denoted $\chi_{\rho}(G)$. The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all sub…

HQMR: Hybrid QoS based Routing Protocol for Wireless Mesh Environment

International audience; Wireless Mesh Networks (WMNs) have been attracting more and more interest from both academic and industrial environments for their seamless broadband connectivity to Internet networks. Besides, providing QoS guarantees for real-time and streaming applications such as Voice over IP (VoIP) and Video on Demand (VoD) is a challenging issue in such environment. Thus, we propose a novel QoS based routing protocol for wireless mesh infrastructure, called Hybrid QoS Mesh Routing (HQMR). Moreover, a clustering algorithm is developed to enhance scalability issues within the mesh infrastructure. HQMR is composed of two routing sub-protocols: a reactive routing protocol for intr…

Paths Coloring Algorithms in Mesh Networks

In this paper, we will consider the problem of coloring directed paths on a mesh network. A natural application of this graph problem is WDM-routing in all-optical networks. Our main result is a simple 4-approximation algorithm for coloring line-column paths on a mesh. We also present sharper results when there is a restriction on the path lengths. Moreover, we show that these results can be extended to toroidal meshes and to line-column or column-line paths.