Search

We initiate the study of multipacking problems for geometric point sets with respect to their Euclidean distances. We consider a set of $n$ points $P$ and define $N_s[v]$ as the subset of $P$ that includes the $s$ nearest points of $v \in P$ and the point $v$ itself. We assume that the \emph{$s$-th neighbor} of each point is unique, for every $s \in \{0, 1, 2, \dots , n-1\}$. For a natural number $r \leq n$, an $r$-multipacking is a set $ M \subseteq P $ such that for each point $ v \in P $ and for every integer $ 1\leq s \leq r $, $|N_s[v]\cap M|\leq (s+1)/2$. The $r$-multipacking number of $ P $ is the maximum cardinality of an $r$-multipacking of $ P $ and is denoted by $ \MP_{r}(P) $. For $r=n-1$, an $r$-multipacking is called a multipacking and $r$-multipacking number is called as multipacking number. We study the problem of computing a maximum $r$-multipacking for point sets in $\mathbb{R}^2$. We show that a maximum $1$-multipacking can be computed in polynomial time but computing a maximum $2$-multipacking is NP complete. Further, we provide approximation and parameterized solutions to the $2$-multipacking problem.

Cops and Robber is a well-studied two-player pursuit-evasion game played on a graph, where a group of cops tries to capture the robber. The \emph{cop number} of a graph is the minimum number of cops required to capture the robber. Gaven\v{c}iak et al.~[Eur. J. of Comb. 72, 45--69 (2018)] studied the game on intersection graphs and established that the cop number for the class of string graphs is at most 15, and asked as an open question to improve this bound for string graphs and subclasses of string graphs. We address this question and establish that the cop number of a string graph is at most 13. To this end, we develop a novel \textit{guarding} technique. We further establish that this technique can be useful for other Cops and Robber games on graphs admitting a representation. In particular, we show that four cops have a winning strategy for a variant of Cops and Robber, named Fully Active Cops and Robber, on planar graphs, addressing an open question of Gromovikov et al.~[Austr. J. Comb. 76(2), 248--265 (2020)]. In passing, we also improve the known bounds on the cop number of boxicity 2 graphs., Comment: A preliminary version appeared in ISAAC 2022

Given a set $P$ of $n$ points in the plane, in general position, denote by $N_\Delta(P)$ the number of empty triangles with vertices in $P$. In this paper we investigate by how much $N_\Delta(P)$ changes if a point $x$ is removed from $P$. By constructing a graph $G_P(x)$ based on the arrangement of the empty triangles incident on $x$, we transform this geometric problem to the problem of counting triangles in the graph $G_P(x)$. We study properties of the graph $G_P(x)$ and, in particular, show that it is kite-free. This relates the growth rate of the number of empty triangles to the famous Ruzsa-Szemer\'edi problem.

For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a dominating broadcast on $ G $. The cost of the dominating broadcast $f$ is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the broadcast domination number of $G$, denoted by $ \gamma_{b}(G) $. A multipacking is a set $ S \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ S $, that is, there are at most $ r $ vertices in $ S $ at a distance at most $ r $ from $ v $ in $ G $. The multipacking number of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. We show that, for any connected chordal graph $G$, $\gamma_{b}(G)\leq \big\lceil{\frac{3}{2} mp(G)\big\rceil}$. We also show that $\gamma_b(G)-mp(G)$ can be arbitrarily large for connected chordal graphs by constructing an infinite family of connected chordal graphs such that the ratio $\gamma_b(G)/mp(G)=10/9$, with $mp(G)$ arbitrarily large. Moreover, we show that $\gamma_{b}(G)\leq \big\lfloor{\frac{3}{2} mp(G)+2\delta\big\rfloor} $ holds for all $\delta$-hyperbolic graphs. In addition, we provide a polynomial-time algorithm to construct a multipacking of a $\delta$-hyperbolic graph $G$ of size at least $ \big\lceil{\frac{2mp(G)-4\delta}{3} \big\rceil} $., Comment: arXiv admin note: text overlap with arXiv:2308.04882

For a graph $G$, $ mp(G) $ is the multipacking number, and $\gamma_b(G)$ is the broadcast domination number. It is known that $mp(G)\leq \gamma_b(G)$ and $\gamma_b(G)\leq 2mp(G)+3$ for any graph $G$, and it was shown that $\gamma_b(G)-mp(G)$ can be arbitrarily large for connected graphs. It is conjectured that $\gamma_b(G)\leq 2mp(G)$ for any general graph $G$. We show that, for any cactus graph $G$, $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$. We also show that $\gamma_b(G)-mp(G)$ can be arbitrarily large for cactus graphs and asteroidal triple-free graphs by constructing an infinite family of cactus graphs which are also asteroidal triple-free graphs such that the ratio $\gamma_b(G)/mp(G)=4/3$, with $mp(G)$ arbitrarily large. This result shows that, for cactus graphs, the bound $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$ cannot be improved to a bound in the form $\gamma_b(G)\leq c_1\cdot mp(G)+c_2$, for any constant $c_1<4/3$ and $c_2$. Moreover, we provide an $O(n)$-time algorithm to construct a multipacking of cactus graph $G$ of size at least $ \frac{2}{3}mp(G)-\frac{11}{3} $, where $n$ is the number of vertices of the graph $G$. The hyperbolicity of the cactus graph class is unbounded. For $0$-hyperbolic graphs, $mp(G)=\gamma_b(G)$. Moreover, $mp(G)=\gamma_b(G)$ holds for the strongly chordal graphs which is a subclass of $\frac{1}{2}$-hyperbolic graphs. Now it's a natural question: what is the minimum value of $\delta$, for which we can say that the difference $ \gamma_{b}(G) - mp(G) $ can be arbitrarily large for $\delta$-hyperbolic graphs? We show that the minimum value of $\delta$ is $\frac{1}{2}$ using a construction of an infinite family of cactus graphs with hyperbolicity $\frac{1}{2}$.

Graph burning is a graph process that models the spread of social contagion. Initially, all the vertices of a graph $G$ are unburnt. At each step, an unburnt vertex is put on fire and the fire from burnt vertices of the previous step spreads to their adjacent unburnt vertices. This process continues till all the vertices are burnt. The burning number $b(G)$ of the graph $G$ is the minimum number of steps required to burn all the vertices in the graph. The burning number conjecture by Bonato et al. states that for a connected graph $G$ of order $n$, its burning number $b(G) \leq \lceil \sqrt{n} \rceil$. It is easy to observe that in order to burn a graph it is enough to burn its spanning tree. Hence it suffices to prove that for any tree $T$ of order $n$, its burning number $b(T) \leq \lceil \sqrt{n} \rceil$ where $T$ is the spanning tree of $G$. It was proved in 2018 that $b(T) \leq \lceil \sqrt{n + n_2 + 1/4} +1/2 \rceil$ for a tree $T$ where $n_2$ is the number of degree $2$ vertices in $T$. In this paper, we provide an algorithm to burn a tree and we improve the existing bound using this algorithm. We prove that $b(T)\leq \lceil \sqrt{n + n_2 + 8}\rceil -1$ which is an improved bound for $n\geq 50$. We also provide an algorithm to burn some subclasses of the binary tree and prove the burning number conjecture for the same.

Graphene oxide (GO) is one of the important functional materials. Large-scale synthesis of it is very challenging. Following a simple cost-effective route, large-scale GO was produced by mechanical (ball) milling, in air, of carbon nanoparticles (CNPs) present in carbon soot in the present study. The thickness of the GO layer was seen to decrease with an increase in milling time. Ball milling provided the required energy to acquire the in-plane graphitic order in the CNPs reducing the disorders in it. As the surface area of the layered structure became more and more with the increase in milling time, more and more oxygen of air got attached to the carbon in graphene leading to the formation of GO. An increase in the time of the ball mill up to 5 hours leads to a significant increase in the content of GO. Thus ball milling can be useful to produce large-scale two-dimensional GO for a short time., Comment: 23 pages, 10 figures

An $(n,m)$-graph is characterised by having $n$ types of arcs and $m$ types of edges. A homomorphism of an $(n,m)$-graph $G$ to an $(n,m)$-graph $H$, is a vertex mapping that preserves adjacency, direction, and type. The $(n,m)$-chromatic number of $G$, denoted by $\chi_{n,m}(G)$, is the minimum value of $|V(H)|$ such that there exists a homomorphism of $G$ to $H$. The theory of homomorphisms of $(n,m)$-graphs have connections with graph theoretic concepts like harmonious coloring, nowhere-zero flows; with other mathematical topics like binary predicate logic, Coxeter groups; and has application to the Query Evaluation Problem (QEP) in graph database. In this article, we show that the arboricity of $G$ is bounded by a function of $\chi_{n,m}(G)$ but not the other way around. Additionally, we show that the acyclic chromatic number of $G$ is bounded by a function of $\chi_{n,m}(G)$, a result already known in the reverse direction. Furthermore, we prove that the $(n,m)$-chromatic number for the family of graphs with a maximum average degree less than $2+ \frac{2}{4(2n+m)-1}$, including the subfamily of planar graphs with girth at least $8(2n+m)$, equals $2(2n+m)+1$. This improves upon previous findings, which proved the $(n,m)$-chromatic number for planar graphs with girth at least $10(2n+m)-4$ is $2(2n+m)+1$. It is established that the $(n,m)$-chromatic number for the family $\mathcal{T}_2$ of partial $2$-trees is both bounded below and above by quadratic functions of $(2n+m)$, with the lower bound being tight when $(2n+m)=2$. We prove $14 \leq \chi_{(0,3)}(\mathcal{T}_2) \leq 15$ and $14 \leq \chi_{(1,1)}(\mathcal{T}_2) \leq 21$ which improves both known lower bounds and the former upper bound. Moreover, for the latter upper bound, to the best of our knowledge we provide the first theoretical proof., Comment: 18 pages

An oriented graph has weak diameter at most $d$ if every non-adjacent pair of vertices are connected by a directed $d$-path. The function $f_d(n)$ denotes the minimum number of arcs in an oriented graph on $n$ vertices having weak diameter $d$. Finding the exact value of $f_d(n)$ is a challenging problem even for $d = 2$. This function was introduced by Katona and Szemeredi (1967), and after that several attempts were made to find its exact value by Znam (1970), Dawes and Meijer (1987), Furedi, Horak, Pareek and Zhu (1998), and Kostochka, Luczak, Simonyi and Sopena (1999) through improving its best known bounds. In that process, it was proved that this function is asymptotically equal to $n\log_2 n$ and hence, is an asymptotically increasing function. However, the exact value and behaviour of this function was not known. In this article, we observe that the oriented graphs with weak diameter at most $2$ are precisely the absolute oriented cliques, that is, analogues of cliques for oriented graphs in the context of oriented coloring. Through studying arc-minimal absolute oriented cliques we prove that $f_2(n)$ is a strictly increasing function. Furthermore, we improve the best known upper bound of $f_2(n)$ and conjecture that our upper bound is tight. This improvement of the upper bound improves known bounds involving the oriented achromatic number.

The weighted $k$-center problem in graphs is a classical facility location problem where we place $k$ centers on the graph, which minimize the maximum weighted distance of a vertex to its nearest center. We study this problem when the underlying graph is a cactus with $n$ vertices and present an $O(n \log^2 n)$ time algorithm for the same. This time complexity improves upon the $O(n^2)$ time algorithm by Ben-Moshe et al. [TCS 2007], which is the current state-of-the-art., Comment: Submitted to Theoretical Computer Science

Ultra-low end-to-end latency is one of the most important requirements in 5G networks and beyond to support latency-critical applications. Cloud-RAN and MEC are considered as the key driving technology that can help reduce end-to-end latency. However, the use of MEC nodes poses radical changes to the access network architecture. As it brings the processing and the networking services closer to the edge, it often requires network functions (for example, the CU/DU stack and the application processing) to be distributed across different MEC sites. Therefore, a novel transport mechanism is needed to efficiently coordinate and connect network functions across MEC nodes. In order to address this challenge, we propose a novel two-tier virtualized PON transport method with schedulers coordination over a virtualised and sliced MESH-PON architecture. While a MESH-PON architecture enables direct communication between MEC nodes that are hosting CU/DU and/or the application processing, our method provides a two tier virtualised PON transport scheme with coordinated schedulers. This approach greatly reduces latency incurred in transporting signals across the different PON tiers, while maintaining the flexibility of the multi-tier methods. We show that our proposed scheme can achieve end-to-end application-level latency below 1ms or 2ms, depending on the network configurations., Comment: 8 pages, 8 figures. arXiv admin note: text overlap with arXiv:2208.10938

In 1975, Plesn\'ik characterized all triangle-free planar graphs as having a diameter $2$. We characterize all triangle-free projective-planar graphs having a diameter $2$ and discuss some applications. In particular, the main result is applied to calculate the analogue of clique numbers for graphs, namely, colored mixed graphs, having different types of arcs and edges.

We propose a mechanism to support URLLC Open-RAN ultra-low latency over a MESH-PON, serving dense deployment of small cell and MEC nodes in an access network. We show the possibility, under given assumptions, to achieve application-to-application end-to-end latency below 1ms., Comment: accepted for publication in ECOC 2022, Sept 18-22

The commercialization of Cloud-RAN, and Open-RAN in particular, is a key factor to enable 5G cell densification, by providing lower cost and more agile deployment of small cells. In addition, the adoption of MEC is important to support ultra-low latency and high reliability required by mission-critical applications, which constitute a milestone of the 5G and beyond vision of a fully connected society. However, connecting antenna site, C-RAN processing and MEC at low cost is challenging, as it requires high-capacity, low latency connectivity delivered through a highly inter-connected topology. While PON is being considered as a solution for providing low-cost connectivity to C-RAN, they only allow data transmission from the endpoints (for example hosting RU at the antenna site) towards a central node (e.g., the central office, hosting computing equipment), thus cannot support traffic from RU towards MEC end nodes that could host DU and possibly CU and network core. This led to research into the evolution of PON architectures with the ability to provide direct communications between endpoints, thus supporting mesh traffic patterns required by MEC installations. In this context, virtualization plays a key role in enabling efficient resource allocation (i.e. optical transmission capacity) to endpoints, according to their communication patterns. In this article, we address the challenge of dynamic allocation of virtual PON slices over mesh-PON architectures to support C-RAN and MEC nodes. We make use of a mixed analytical-iterative model to compute optimal virtual PON slice allocation, with the objective of minimizing the use of MEC node resources, while meeting a target latency threshold (100 $\mu s$ in our scenario). Our method is particularly effective in reducing computation time, enabling virtual PON slice allocation in timescales compatible with real-time or near real-time operations.

Given a matching between n red points and n blue points by line segments in the plane, we consider the problem of obtaining a crossing-free matching through flip operations that replace two crossing segments by two non-crossing ones. We first show that (i) it is NP-hard to alpha-approximate the shortest flip sequence, for any constant alpha. Second, we show that when the red points are colinear, (ii) given a matching, a flip sequence of length at most n(n-1)/2 always exists, and (iii) the number of flips in any sequence never exceeds (n(n-1)/2) (n+4)/6. Finally, we present (iv) a lower bounding flip sequence with roughly 1.5 n(n-1)/2 flips, which shows that the n(n-1)/2 flips attained in the convex case are not the maximum, and (v) a convex matching from which any flip sequence has roughly 1.5 n flips. The last four results, based on novel analyses, improve the constants of state-of-the-art bounds., Comment: 28 pages, 27 figures, accepted at EuroCG 2022, at CORE 2022 (ICALP Workshop), at LATIN 2022, and at CGTA 2022 (EuroCG 2022 special issue)

We introduce the fractional version of oriented coloring and initiate its study. We prove some basic results and study the parameter for directed cycles and sparse planar graphs. In particular, we show that for every $\epsilon > 0$, there exists an integer $g_{\epsilon} \geq 12$ such that any oriented planar graph having girth at least $g_{\epsilon}$ has fractional oriented chromatic number at most $4+\epsilon$. Whereas, it is known that there exists an oriented planar graph having girth at least $g_{\epsilon}$ with oriented chromatic number equal to $5$. We also study the fractional oriented chromatic number of directed cycles and provide its exact value. Interestingly, the result depends on the prime divisors of the length of the directed cycle., Comment: 15 pages

As progressive densification of cells, deployment of Cloud-RAN and \ac{MEC} are coming into reality to support the ultra-low latency with high reliability in 5G and beyond, it generates mesh traffic pattern across fronthaul network. This led to evolution of PON architectural enhancements with virtualization in order to support such mesh traffic pattern. However, allocation of virtual PON slices dynamically over such mesh-PON based fronthaul transport is becoming a research challenge. In this paper, we provide a mixed analytical-iterative model to compute optimal virtual PON slice allocation, providing mesh access connectivity with ultra-low end-to-end latency in next-generation MEC-based Cloud-RAN. Our proposed method can compute optimal virtual PON slice allocation in timescales compatible with real-time or near real-time operations., Comment: 5 pages, 5 Figures