Partition dimension of disjoint union of complete bipartite graphs
For any (not necessary connected) graph $G(V,E)$ and $A\subseteq V(G)$, the distance of a vertex $x\in V(G)$ and $A$ is $d(x,A)=\min\{d(x,a): a\in A\}$. A subset of vertices $A$ resolves two vertices $x,y \in V(G)$ if $d(x,A)\neq d(y,A)$. For an ordered partition $\Lambda=\{A_1, A_2,\ldots, A_k\}$ o...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | Indonesian |
| Published: |
Universitas Islam Negeri Raden Intan Lampung
2021-07-01
|
| Series: | Desimal |
| Subjects: | |
| Online Access: | http://ejournal.radenintan.ac.id/index.php/desimal/article/view/10190 |
| _version_ | 1818971137439170560 |
|---|---|
| author | Debi Oktia Haryeni Edy Tri Baskoro Suhadi Wido Saputro |
| author_facet | Debi Oktia Haryeni Edy Tri Baskoro Suhadi Wido Saputro |
| author_sort | Debi Oktia Haryeni |
| collection | DOAJ |
| description | For any (not necessary connected) graph $G(V,E)$ and $A\subseteq V(G)$, the distance of a vertex $x\in V(G)$ and $A$ is $d(x,A)=\min\{d(x,a): a\in A\}$. A subset of vertices $A$ resolves two vertices $x,y \in V(G)$ if $d(x,A)\neq d(y,A)$. For an ordered partition $\Lambda=\{A_1, A_2,\ldots, A_k\}$ of $V(G)$, if all $d(x,A_i)\infty$ for all $x\in V(G)$, then the representation of $x$ under $\Lambda$ is $r(x|\Lambda)=(d(x,A_1), d(x,A_2), \ldots, d(x,A_k))$. Such a partition $\Lambda$ is a resolving partition of $G$ if every two distinct vertices $x,y\in V(G)$ are resolved by $A_i$ for some $i\in [1,k]$. The smallest cardinality of a resolving partition $\Lambda$ is called a partition dimension of $G$ and denoted by $pd(G)$ or $pdd(G)$ for connected or disconnected $G$, respectively. If $G$ have no resolving partition, then $pdd(G)=\infty$. In this paper, we studied the partition dimension of disjoint union of complete bipartite graph, namely $tK_{m,n}$ where $t\geq 1$ and $m\geq n\geq 2$. We gave the necessary condition such that the partition dimension of $tK_{m,n}$ are finite. Furthermore, we also derived the necessary and sufficient conditions such that $pdd(tK_{m,n})$ is either equal to $m$ or $m+1$. |
| first_indexed | 2024-12-20T14:47:36Z |
| format | Article |
| id | doaj.art-1b006b610b3a40d0b94ee6ca936fcae9 |
| institution | Directory Open Access Journal |
| issn | 2613-9073 2613-9081 |
| language | Indonesian |
| last_indexed | 2024-12-20T14:47:36Z |
| publishDate | 2021-07-01 |
| publisher | Universitas Islam Negeri Raden Intan Lampung |
| record_format | Article |
| series | Desimal |
| spelling | doaj.art-1b006b610b3a40d0b94ee6ca936fcae92022-12-21T19:37:04ZindUniversitas Islam Negeri Raden Intan LampungDesimal2613-90732613-90812021-07-014222523010.24042/djm.v4i2.101904161Partition dimension of disjoint union of complete bipartite graphsDebi Oktia Haryeni0Edy Tri Baskoro1Suhadi Wido Saputro2The Republic of Indonesia Defense UniversityInstitut Teknologi BandungInstitut Teknologi BandungFor any (not necessary connected) graph $G(V,E)$ and $A\subseteq V(G)$, the distance of a vertex $x\in V(G)$ and $A$ is $d(x,A)=\min\{d(x,a): a\in A\}$. A subset of vertices $A$ resolves two vertices $x,y \in V(G)$ if $d(x,A)\neq d(y,A)$. For an ordered partition $\Lambda=\{A_1, A_2,\ldots, A_k\}$ of $V(G)$, if all $d(x,A_i)\infty$ for all $x\in V(G)$, then the representation of $x$ under $\Lambda$ is $r(x|\Lambda)=(d(x,A_1), d(x,A_2), \ldots, d(x,A_k))$. Such a partition $\Lambda$ is a resolving partition of $G$ if every two distinct vertices $x,y\in V(G)$ are resolved by $A_i$ for some $i\in [1,k]$. The smallest cardinality of a resolving partition $\Lambda$ is called a partition dimension of $G$ and denoted by $pd(G)$ or $pdd(G)$ for connected or disconnected $G$, respectively. If $G$ have no resolving partition, then $pdd(G)=\infty$. In this paper, we studied the partition dimension of disjoint union of complete bipartite graph, namely $tK_{m,n}$ where $t\geq 1$ and $m\geq n\geq 2$. We gave the necessary condition such that the partition dimension of $tK_{m,n}$ are finite. Furthermore, we also derived the necessary and sufficient conditions such that $pdd(tK_{m,n})$ is either equal to $m$ or $m+1$.http://ejournal.radenintan.ac.id/index.php/desimal/article/view/10190resolvabilitymetric dimensionpartition dimensiondisconnected graphforestcomplete bipartite graph. |
| spellingShingle | Debi Oktia Haryeni Edy Tri Baskoro Suhadi Wido Saputro Partition dimension of disjoint union of complete bipartite graphs Desimal resolvability metric dimension partition dimension disconnected graph forest complete bipartite graph. |
| title | Partition dimension of disjoint union of complete bipartite graphs |
| title_full | Partition dimension of disjoint union of complete bipartite graphs |
| title_fullStr | Partition dimension of disjoint union of complete bipartite graphs |
| title_full_unstemmed | Partition dimension of disjoint union of complete bipartite graphs |
| title_short | Partition dimension of disjoint union of complete bipartite graphs |
| title_sort | partition dimension of disjoint union of complete bipartite graphs |
| topic | resolvability metric dimension partition dimension disconnected graph forest complete bipartite graph. |
| url | http://ejournal.radenintan.ac.id/index.php/desimal/article/view/10190 |
| work_keys_str_mv | AT debioktiaharyeni partitiondimensionofdisjointunionofcompletebipartitegraphs AT edytribaskoro partitiondimensionofdisjointunionofcompletebipartitegraphs AT suhadiwidosaputro partitiondimensionofdisjointunionofcompletebipartitegraphs |