Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set $V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed \emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$, and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-se...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2022-02-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/8440/pdf |
| _version_ | 1797269990913605632 |
|---|---|
| author | Márcia R. Cappelle Erika Coelho Les R. Foulds Humberto J. Longo |
| author_facet | Márcia R. Cappelle Erika Coelho Les R. Foulds Humberto J. Longo |
| author_sort | Márcia R. Cappelle |
| collection | DOAJ |
| description | Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set
$V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed
\emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$,
and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set for
short) if no two vertices in $G$ have the same set of neighbors in $S$, and
each vertex in $S$ is open-dominated exactly once by $S$. The problem of
deciding whether or not $G$ has an $OLD_{oind}$-set has important applications
that have been reported elsewhere. As the problem is known to be
$\mathcal{NP}$-complete, it appears to be notoriously difficult as we show that
its complexity remains the same even for just planar bipartite graphs of
maximum degree five and girth six, and also for planar subcubic graphs of girth
nine. Also, we present characterizations of both $P_4$-tidy graphs and the
complementary prisms of cographs that have an $OLD_{oind}$-set. |
| first_indexed | 2024-03-11T21:31:35Z |
| format | Article |
| id | doaj.art-24a89219a1a94852a4be224b301027b4 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:09Z |
| publishDate | 2022-02-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-24a89219a1a94852a4be224b301027b42024-03-07T15:46:22ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502022-02-01vol. 24, no. 1Graph Theory10.46298/dmtcs.84408440Open-independent, open-locating-dominating sets: structural aspects of some classes of graphsMárcia R. CappelleErika CoelhoLes R. FouldsHumberto J. LongoLet $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set $V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed \emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$, and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set for short) if no two vertices in $G$ have the same set of neighbors in $S$, and each vertex in $S$ is open-dominated exactly once by $S$. The problem of deciding whether or not $G$ has an $OLD_{oind}$-set has important applications that have been reported elsewhere. As the problem is known to be $\mathcal{NP}$-complete, it appears to be notoriously difficult as we show that its complexity remains the same even for just planar bipartite graphs of maximum degree five and girth six, and also for planar subcubic graphs of girth nine. Also, we present characterizations of both $P_4$-tidy graphs and the complementary prisms of cographs that have an $OLD_{oind}$-set.https://dmtcs.episciences.org/8440/pdfcomputer science - discrete mathematics |
| spellingShingle | Márcia R. Cappelle Erika Coelho Les R. Foulds Humberto J. Longo Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics |
| title | Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs |
| title_full | Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs |
| title_fullStr | Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs |
| title_full_unstemmed | Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs |
| title_short | Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs |
| title_sort | open independent open locating dominating sets structural aspects of some classes of graphs |
| topic | computer science - discrete mathematics |
| url | https://dmtcs.episciences.org/8440/pdf |
| work_keys_str_mv | AT marciarcappelle openindependentopenlocatingdominatingsetsstructuralaspectsofsomeclassesofgraphs AT erikacoelho openindependentopenlocatingdominatingsetsstructuralaspectsofsomeclassesofgraphs AT lesrfoulds openindependentopenlocatingdominatingsetsstructuralaspectsofsomeclassesofgraphs AT humbertojlongo openindependentopenlocatingdominatingsetsstructuralaspectsofsomeclassesofgraphs |