ﻻ يوجد ملخص باللغة العربية
The $r$-th iterated line graph $L^{r}(G)$ of a graph $G$ is defined by: (i) $L^{0}(G) = G$ and (ii) $L^{r}(G) = L(L^{(r- 1)}(G))$ for $r > 0$, where $L(G)$ denotes the line graph of $G$. The Hamiltonian Index $h(G)$ of $G$ is the smallest $r$ such that $L^{r}(G)$ has a Hamiltonian cycle. Checking if $h(G) = k$ is NP-hard for any fixed integer $k geq 0$ even for subcubic graphs $G$. We study the parameterized complexity of this problem with the parameter treewidth, $tw(G)$, and show that we can find $h(G)$ in time $O*((1 + 2^{(omega + 3)})^{tw(G)})$ where $omega$ is the matrix multiplication exponent and the $O*$ notation hides polynomial factors in input size. The NP-hard Eulerian Steiner Subgraph problem takes as input a graph $G$ and a specified subset $K$ of terminal vertices of $G$ and asks if $G$ has an Eulerian (that is: connected, and with all vertices of even degree.) subgraph $H$ containing all the terminals. A second result (and a key ingredient of our algorithm for finding $h(G)$) in this work is an algorithm which solves Eulerian Steiner Subgraph in $O*((1 + 2^{(omega + 3)})^{tw(G)})$ time.
We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed gra
An extension of the well-known Szeged index was introduced recently, named as weighted Szeged index ($textrm{sz}(G)$). This paper is devoted to characterizing the extremal trees and graphs of this new topological invariant. In particular, we proved t
textit{Voronoi game} is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underly
A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$, i.e., bonds are cut-sets that determine cuts $[S,Vsetminus S]$ of $G$ such that $G[S]$ and $G[Vsetminus S]$ are both connected. Given $s,tin V(G)$, an $st$-bond of $G$ is a
We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of the Held-Karp linear programming relaxation has bounded orientable genus.