Source author record

Isma Bouchemakh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

On the Broadcast Independence Number of Circulant Graphs

An independent broadcast on a graph $G$ is a function $f: V \longrightarrow \{0,\ldots,{\rm diam}(G)\}$ such that $(i)$ $f(v)\leq e(v)$ for every vertex $v\in V(G)$ , where $\operatorname{diam}(G)$ denotes the diameter of $G$ and $e(v)$ the eccentricity of vertex $v$ , and $(ii)$ $d(u,v) > \max \{f(u), f(v)\}$ for every two distinct vertices $u$ and $v$ with $f(u)f(v)>0$ . The broadcast independence number $β_b(G)$ of $G$ is then the maximum value of $\sum_{v \in V} f(v)$ , taken over all independent broadcasts on $G$ . We prove that every circulant graph of the form $C(n;1,a)$ , $3\le a\le \lfloor\frac{n}{2} \rfloor$ , admits an optimal $2$ -bounded independent broadcast, that is, an independent broadcast~ $f$ satisfying $f(v)\le 2$ for every vertex $v$ , except when $n=2a+1$ , or $n=2a$ and $a$ is even. We then determine the broadcast independence number of various classes of such circulant graphs, and prove that, for most of these classes, the equality $β_b(C(n;1,a)) = α(C(n;1,a))$ holds, where $α(C(n;1,a))$ denotes the independence number of $C(n;1,a)$ .

preprint2020arXiv

Broadcasts on Paths and Cycles

A broadcast on a graph $G=(V,E)$ is a function $f: V\longrightarrow \{0,\ldots,\operatorname{diam}(G)\}$ such that $f(v)\leq e\_G(v)$ for every vertex $v\in V$ , where $\operatorname{diam}(G)$ denotes the diameter of $G$ and $e\_G(v)$ the eccentricity of $v$ in $G$ . The cost of such a broadcast is then the value $\sum\_{v\in V}f(v)$ .Various types of broadcast functions on graphs have been considered in the literature, in relation with domination, irredundence, independenceor packing, leading to the introduction of several broadcast numbers on graphs.In this paper, we determine these broadcast numbers for all paths and cycles, thus answering a questionraised in [D.~Ahmadi, G.H.~Fricke, C.~Schroeder, S.T.~Hedetniemi and R.C.~Laskar, Broadcast irredundance in graphs. {\it Congr. Numer.} 224 (2015), 17--31].

preprint2016arXiv

2-Distance Colorings of Integer Distance Graphs

A 2-distance k-coloring of a graph G is a mapping from V (G) to the set of colors {1,. .. , k} such that every two vertices at distance at most 2 receive distinct colors. The 2-distance chromatic number $χ$ 2 (G) of G is then the mallest k for which G admits a 2-distance k-coloring. For any finite set of positive integers D = {d 1 ,. .. , d k }, the integer distance graph G = G(D) is the infinite graph defined by V (G) = Z and uv $\in$ E(G) if and only if |v -- u| $\in$ D. We study the 2-distance chromatic number of integer distance graphs for several types of sets D. In each case, we provide exact values or upper bounds on this parameter and characterize those graphs G(D) with $χ$ 2 (G(D)) = Δ(G(D)) + 1.

preprint2016arXiv

Packing Coloring of Undirected and Oriented Generalized Theta Graphs

The packing chromatic number $χ$ $ρ$ (G) of an undirected (resp. oriented) graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V 1,..., V k, in such a way that every two distinct vertices in V i are at distance (resp. directed distance) greater than i in G for every i, 1 $\le$ i $\le$ k. The generalized theta graph $Θ$ {\ell} 1,...,{\ell}p consists in two end-vertices joined by p $\ge$ 2 internally vertex-disjoint paths with respective lengths 1 $\le$ {\ell} 1 $\le$ . . . $\le$ {\ell} p. We prove that the packing chromatic number of any undirected generalized theta graph lies between 3 and max{5, n 3 + 2}, where n 3 = |{i / 1 $\le$ i $\le$ p, {\ell} i = 3}|, and that both these bounds are tight. We then characterize undirected generalized theta graphs with packing chromatic number k for every k $\ge$ 3. We also prove that the packing chromatic number of any oriented generalized theta graph lies between 2 and 5 and that both these bounds are tight.

preprint2015arXiv

Packing coloring of some undirected and oriented coronae graphs

The packing chromatic number $\pcn(G)$ of a graph $G$ is the smallest integer $k$ such that its set of vertices $V(G)$ can be partitioned into $k$ disjoint subsets $V\_1$ , \ldots, $V\_k$ , in such a way that every two distinct vertices in $V\_i$ are at distance greater than $i$ in $G$ for every $i$ , $1\le i\le k$ . For a given integer $p \ge 1$ , the generalized corona $G\odot pK\_1$ of a graph $G$ is the graph obtained from $G$ by adding $p$ degree-one neighbors to every vertex of $G$ . In this paper, we determine the packing chromatic number of generalized coronae of paths and cycles. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of generalized coronae of paths and cycles.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.