\documentclass{template-jurnal} %Bagian ini diedit oleh editor Jurnal Matematika UNAND \hyphenation{di-tulis-kan di-terang-kan} \hyphenation{Misal-kan identifi-kasi sedang-kan mem-punyai pe-milihan} %Perhatikan aturan penulisan dan ukuran huruf yang digunakan \begin{document} \markboth{Kristiana Wijaya} %Jika lebih dari dua penulis, tuliskan sebagai Nama Penulis Pertama dkk. {Dimensi metrik dari graf hasil identifikasi} %%%%%%%%%%%%%%%%%%%%% Publisher's Area please ignore %%%%%%%%%%%%%%% % \catchline{}{}{}{}{} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{DIMENSI METRIK DARI GRAF HASIL IDENTIFIKASI} %\author{KRISTIANA WIJAYA} %\address{Graph and Algebra Research Group, Jurusan Matematika \\Fakultas Matematika dan Ilmu Pengetahuan Alam\\ Universitas Jember\\ Jl. Kalimantan 37 Jember 68121, Jawa Timur, Indonesia\\ %$^{b}$ Instansi Penulis Kedua,\\ %$^{c}$ Instansi Penulis Ketiga.\\ %email : \email{kristiana.fmipa@unej.ac.id}} \maketitle \setcounter{page}{1} %bagian ini diedit oleh editor Jurnal Matematika UNAND \begin{abstract} \begin{center} Diterima ..... \quad Direvisi ..... \quad Dipublikasikan ..... %tanggal-tanggal tersebut \textbf{dikosongkan} saja \end{center} \bigskip \textbf{Abstrak}. %Dalam bahasa Indonesia Pada paper ini dibahas mengenai dimensi metrik dari graf hasil identifikasi. Dimensi metrik dari sebuah graf $G,$ dinotasikan dengan $dim(G),$ adalah kardinalitas paling kecil dari setiap himpunan pembeda di $G.$ Poisson dan Zhang telah memberikan batas bawah dan atas dimensi metrik dari graf hasil identifikasi. Pada paper ini dibahas dimensi metrik dari graf reguler yang diidentifikasi dengan graf lintasan. Selain itu, diberikan juga kelas-kels graf yang hasil identifikasinya mempunyai dimensi metrik tepat sama dengan batas bawah yang dihasilkan oleh Poisson dan Zhang. \bigskip \textbf{Abstract}. % Dalam bahasa Inggris \textit{This paper is about the metric dimension of a graph formed by identifying two graphs. A \textit{metric dimension} of $G$, denoted by $dim(G)$, is the minimum cardinality of any resolving set of $G$. % Poisson and Zhang have given lower and upper bounds of the metric dimension of identification of two graphs. Here we discuss the metric dimension of the graph obtained from identifying a regular and path graph. Furthermore, we give some classes of graphs (by identification) having the metric dimension the same as the lower bound by Poisson and Zhang.} \end{abstract} \keywords{Dimensi metrik, himpunan pembeda, identifikasi dua graf} \section{Pendahuluan} Graf yang dibahas pada paper ini adalah graf sederhana (tanpa {\it loop} dan sisi paralel), terhubung, tidak berarah, dan berhingga. % {\it Jarak} dari titik $u$ ke $v$ pada graf $G$ adalah panjang lintasan terpendek dari titik $u$ ke $v$. Misalkan $W=\{w_1, w_2, \ldots, w_k\}$ adalah subhimpunan terurut dari himpunan titik $V(G)$. Yang dimaksud representasi titik $u$ di $G$ terhadap himpunan $W,$ dinotasikan $r(u|W),$ adalah $k-tuple$ terurut dari jarak titik $u$ ke setiap titik di $W,$ yaitu $r(u|W)=(d(u, w_1), d(u, w_2), \ldots, d(u, w_k)).$ Jika setiap titik di $G$ mempunyai representasi yang berbeda terhadap $W,$ maka $W$ disebut sebagai {\it himpunan pembeda} ({\it resolving set}). Jelas bahwa himpunan pembeda dari sebuah graf tidaklah tunggal. Himpunan pembeda dengan kardinalitas minimum disebut {\it basis}. Kardinalitas dari basis dinamakan {\it dimensi metrik} dari suatu graf, dinotasikan $dim(G).$ Konsep dimensi metrik ini diperkenalkan oleh Slater \cite{Slater75} dan juga oleh Harary dan Melter \cite{Harary} secara independen. %Pada umumnya permasalahan mendapatkan himpunan basis untuk suatu graf adalah permasalahan NP-complete. %Penelitian pada area ini adalah mendapatkan dimensi metrik pada suatu kelas graf atau mengkarakterisasi graf dengan dimensi metrik tertentu. Chartrand et al. \cite{Chartrand} telah mengkarakterisasi semua graf yang mempunyai dimensi metrik $1, n-1$ dan $n-2,$ dengan $n$ menyatakan banyak titik dari graf $G,$ melalui teorema berikut. \begin{theorem} $\cite{Chartrand}$ Misalkan $G$ adalalah graf terhubung dengan banyak titik $n \geq 2.$ \begin{enumerate} \item[$(a)$] $dim(G)=1$ jika dan hanya jika $G$ adalah graf lintasan dengan $n$ titik, $P_n.$ \item[$(b)$] $dim(G)=n-1$ jika dan hanya jika $G$ adalah graf lengkap dengan $n$ titik, $K_n.$ \item[$(c)$] $dim(G)=n-2$ dengan $n \geq 4$ jika dan hanya jika $G$ adalah \begin{itemize} \item graf bipartisi lengkap $K_{r,s}$ $(r,s \geq 1)$ dengan $n=r+s,$ \item graf hasil operasi join dari graf lengkap dengan $r$ titik dan graf kosong dengan $s$ titik, $K_r + \overline{K}_s$ ($r \geq 1, s \geq 2$), atau \item graf hasil operasi join dari graf lengkap dengan $r$ titik dan graf lengkap dengan $s$ titik dan satu titik terisolasi, $K_r + (K_1 \cup K_s)$ ($r, s \geq 1$). \end{itemize} \end{enumerate} \label{char} \end{theorem} % \noindent Selain itu, Chartrand et al. \cite{Chartrand} juga memberikan dimensi metrik dari graf lingkaran dan graf pohon selain lintasan. Graf lingkaran dengan $n \geq 3$ titik, $C_n,$ mempunyai dimensi metrik 2, $dim(C_n)=2.$ Berdasarkan Teorema \ref{char}, dimensi metrik dari sebarang graf terhubung selain graf yang disebut pada Teorema \ref{char} adalah $2 \leq dim(G) \leq n-3$. % Graf pohon $T_n$ dengan $n \geq3$ titik yang bukan merupakan graf lintasan, dimensi metriknya %bergantung dari titik mayor dari graf pohon, bahwa adalah $dim(T_n)= \sigma(T_n) - ex(T_n),$ dengan $\sigma(T_n)$ menyatakan jumlah dari derajat titik mayor dan $ex(T_n)$ menyatakan titik mayor eksterior dari $T_n$. %Yang dimaksud {\it titik mayor} di $G$ adalah titik yang mempunyai derajat tiga atau lebih. Setiap titik daun $u$ dinamakan {\it titik terminal} dari titik mayor $v$ di $G$ jika $d(u,v) < d(u,w)$ untuk setiap titik mayor $w$ di $G.$ Selanjutnya derajat terminal, dinotasikan $ter(v)$ dari titik mayor $v$ adalah banyaknya titik terminal dari $v.$ Titik mayor $v$ disebut {\it titik mayor eksterior} jika titik tersebut mempunyai derajat terminal positif. % Beberapa kelas graf yang telah dikaji dimensi metriknya antara lain graf Johnson dan Kneser \cite{Bailey}, graf {\it fullerene}\cite{Akhter}, graf unisiklis \cite{Dudenko, Dudenko18}, graf bunga $f_{m \times n}$ \cite{Imran13}, {\it Nanotubes} \cite{Siddiq15, Siddiq14}, graf tangga segitiga \cite{anggraeni}, graf dual antiprisma \cite{fitri}, graf naga \cite{Marinda}, graf {\it buckminsterfullerene} \cite{putrih}, graf barbel \cite{rahma}. Beberapa graf hasil operasi amalgamasi \cite{febri, iswadi, putrif}, Cartesius \cite{mayora, pdwi, rahmi}, {\it join} \cite{putra, riyan}, {\it comb product} \cite{saputro}, subdivisi \cite{pratama} telah diperoleh dimensi metriknya. Poisson dan Zhang \cite{poisson} telah memberikan batas bawah dan batas atas dimensi metrik dari graf hasil identifikasi. Misalkan $G$ dan $H$ graf dengan titik $u \in V(G)$ dan $v \in V(H).$ {\it Identifikasi} dari dua graf $G$ dan $H$ pada titik yang telah ditentukan, yaitu $u \in V(G)$ dan $v \in V(H)$, dinotasikan dengan $G \odot_{u=v} H$ (cukup ditulis $G \odot H$), adalah graf yang diperoleh dari graf $G$ dan $H$ dengan titik $u \in V(G)$ diidentifikasi atau dilekatkan pada titik $v \in V(H).$ Dengan demikian, jika graf $G$ mempunyai $p$ titik dan $r$ sisi dan graf $H$ mempunyai $q$ titik dan $s$ sisi maka graf $G \odot_{u=v} H$ mempunyai $p+q-1$ titik dan $r+s$ sisi. Dalam hal ini, titik $u$ dan $v$ disebut {\it titik identifikasi}. Jelas bahwa operasi identifikasi dari graf $G$ dan $H$ bersifat komutatif. Namun demikian graf hasil identifikasi bergantung pada titik yang dipilih sebagai titik identifikasi, kecuali jika $G$ dan $H$ adalah graf reguler, yaitu graf yang setiap titiknya berderajat sama. Sebagai contoh, identifikasi dari graf lintasan dengan tiga titik, $P_3,$ dan graf lintasan dengan dua titik, $P_2,$ adalah graf lintasan dengan empat titik, $P_4,$ jika titik identifikasi yang dipilih di $P_3$ adalah titik daun. Sedangkan jika titik identifikasinya adalah titik berderajat dua di $P_3,$ hasil identifikasinya adalah graf bintang dengan tiga titik daun, $S_{3}.$ {\it Titik daun} adalah titik yang berderajat satu di sebuah graf. Batas bawah dimensi metrik dari graf hasil identifikasi oleh Poisson dan Zhang \cite{poisson} diberikan pada teorema berikut. %======================================================================= \begin{theorem} \label{zhang}$\cite{poisson}$ Misalkan $G$ dan $H$ adalah graf terhubung dengan order lebih dari dua, $u \in V(G)$ dan $v \in V(H)$. Batas bawah dari dimensi metrik dari graf identifikasi $G \odot H$ di titik identifikasi $u=v$ adalah \[dim(G \odot H) \geq dim(G) + dim(H) -2.\] \end{theorem} %======================================================================= Fokus dari penelitian ini adalah mengkaji dimensi metrik dari graf hasil identifikasi. Pada paper ini diberikan graf yang dimensi metrik dari hasil identifikasinya, $G \odot H,$ tidak berubah atau tetap, yaitu bahwa $dim(G \odot H) = dim(G).$ Selain itu diberikan juga beberapa kelas graf $G$ dan $H$ yang dimensi metrik dari hasil identifikasinya, $G \odot H,$ tepat sama dengan nilai batas bawah dari Poisson dan Zhang \cite{poisson} pada Teorema \ref{zhang}, bahwa $dim(G \odot H) = dim(G) + dim(H) -2.$ Terlebih dahulu akan diberikan beberapa dimensi metrik dari graf hasil identifikasi dari beberapa kelas graf pohon. %Operasi identifikasi dari dua buah graf adalah amalgamasi dari dua buah graf. Iswadi et al. \bibitem{iswadi} telah mendapatkan dimensi metrik dari amalgamsi graf lingkaran, sebagai berikut. \section{Hasil dan Pembahasan} % Misalkan kedua graf $G$ dan $H$ adalah kelas graf pohon. Graf hasil identifikasi $G$ dan $H$ %, $G \odot H$, adalah kelas graf pohon juga. Berdasarkan hasil dari Chartrand et al. \cite{Chartrand} tentang dimensi metrik dari graf pohon, dimensi metrik dari $G \odot H$ untuk $G$ dan $H$ graf lintasan atau graf bintang dapat ditentukan dengan mudah. Graf lintasan dengan $n$ titik, dinotasikan $P_n,$ adalah graf terhubung yang tidak memuat lingkaran dan mempunyai tepat dua titik daun. Sedangkan graf bintang dengan $n+1$ titik, dinotasikan $S_n,$ adalah graf terhubung yang mempunyai $n$ titik daun. %Misalkan $P_m$ dan $P_n$ adalah graf lintasan dengan $m$ dan $n$ titik secara berturut-turut. Dimensi metrik dari $P_m \odot P_n$ %bergantung pada pemilihan titik identifikasi di masing-masing graf. Jelas bahwa jika kedua titik identifikasi adalah titik daun, maka $P_m \odot P_n$ adalah graf lintasan dengan $m+n-1$ titik, sehingga $dim(P_m \odot P_n) = 1$. Jika hanya satu titik identifikasi yang merupakan titik daun, maka$ P_m \odot P_n$ adalah graf pohon dengan sebuah titik mayor berderajat $3$ dan tiga buah titik daun, sehingga $dim(P_m \odot P_n) = 2$. Sedangkan jika kedua titik identifikasi bukan titik daun, maka $P_m \odot P_n$ adalah graf pohon dengan sebuah titik mayor berderajat $4$ dan empat buah titik daun, sehingga $dim(P_m \odot P_n) = 3.$ Sehingga Dimensi metrik dari graf hasil indentifikasi dua graf lintasan adalah: \[dim(P_m \odot P_n) = \left\{ \begin{array}{ll} 1 \quad & \mbox{jika kedua titik identifikasi adalah titik daun},\\ 2 & \mbox{jika salah satu saja titik identifikasi adalah titik daun},\\ 3 & \mbox{jika kedua titik identifikasi bukan titik daun}. \end{array}\right.\] %-------------------------------------------------------------------------------------------------------------------------------------------------- %Seperti halnya graf lintasan, \noindent Sedangkan dimensi metrik dari graf hasil identifikasi dua graf bintang $S_m$ dan $S_n$ dengan $m$ dan $n$ titik daun secara berturut-turut adalah: % %\begin{corollary} \label{2star}. %Untuk setiap $m$ dan $n$ bilangan bulat positif yang lebih besar dari $1$, \[dim(S_{m} \odot S_{n}) = \left\{\begin{array}{ll} m+n-1 \qquad & \mbox{jika titik identifikasi adalah titik pusat},\\ m+n-4 & \mbox{jika titik identifikasi adalah titik daun},\\ m+n-3 & \mbox{lainnya.} \end{array}\right.\] %\end{corollary} % %\begin{corollary} \label{2ps}. % Selanjutnya dimensi metrik dari graf hasil identifikasi graf bintang $S_m$ dan graf lintasan $P_n$ adalah: %Untuk setiap $m$ dan $n$ bilangan bulat positif yang lebih besar dari $1$, \[dim(S_{m} \odot P_{n}) = \left\{\begin{array}{ll} m-1 \qquad & \mbox{jika titik identifikasi adalah titik daun},\\ m & \mbox{jika titik identifikasi adalah titik pusat dari graf}\\ & \mbox{bintang dan titik daun dari graf lintasan},\\ m+1 & \mbox{lainnya.} \end{array}\right.\] %\end{corollary} % Sebagai contoh, dimensi metrik dari identifikasi dua graf bintang berdasarkan pemilihan titik identifikasinya, dapat dilihat pada Gambar \ref{2st}. Graf bintang pertama digambar dengan sisi warna biru dan graf bintang kedua dengan sisi warna hitam, untuk mempermudah dalam melihat titik identifikasi dari masing-masing graf. Dalam hal ini, basis dari identifikasi graf bintang adalah titik-titik yang berwarna. Sedangkan titik berwarna putih adalah titik-titik yang tidak menjadi anggota basis. \begin{figure}[htbp] \begin{center} \includegraphics[width=12cm]{A/star} \caption{Dimensi metrik graf hasil identifikasi dua graf bintang sesuai dengan pemilihan titik identifikasinya} % $C_{14}[(4,P_2); (1,2,3)].$} \label{2st} \end{center} \end{figure} %-------------------------------------------------------------------------------------------------------------------------------------------------- % Misalkan $G$ adalah graf reguler berderajar $r \geq 1.$ Hasil identifikasi dari graf reguler $G$ dan graf lintasan $P_n$ tidak bergantung pada pemilihan titik identifikasi di graf $G$, tetapi pemilihan titik identifikasi di graf $P_n$. Pada teorema berikut dibuktikan bahwa jika titik identifikasi dari graf lintasan $P_n$ adalah titik daunnya, maka dimensi metrik dari $G \odot P_n$ sama dengan dimensi metrik dari graf reguler $G.$ %----------------------------------------------------------------------------------------------------------------------------------------------------- \begin{theorem} \label{reg} Misalkan $G$ graf reguler dan $P_n$ graf lintasan dengan $n$ titik. Misalkan pula $u$ titik di $G$. Jika titik identifikasi $v \in V(P_n)$ adalah titik daun, maka \[dim(G \odot P_n) = dim(G).\] \end{theorem} % \begin{proof} Untuk graf reguler dengan derajat satu, maka $G=K_2$, sehingga $dim(G \odot P_n) = dim(G).$ %Sedangkan untuk graf reguler dengan derajat dua, $G$ adalah graf lingkaran. Jelas bahwa $dim(C_m \odot P_n) = dim(C_m)=2$ dengan himpunan basis di $dim(C_m \odot P_n)$ sama dengan himpunan basis di $C_m.$ Selanjutnya, misalkan $G$ merupakan graf reguler dengan derajat $r \geq 2.$ % Pertama, akan dibuktikan bahwa $dim(G \odot P_n) \geq dim(G)$. Akan ditunjukkan bahwa setiap himpunan $W$ dengan kardinalitas $\dim(G)-1$ bukanlah himpunan pembeda di $G \odot P_n.$ Jelas bahwa jika semua titik di $W$ diambil dari titik di $V(G)$ maka terdapat dua titik di $G$ dengan representasi yang sama. Sedangkan jika sebanyak $\dim(G)-1$ titik hanya berasal dari graf lintasan $P_n,$ maka terdapat dua titik $x$ dan $y$ di $G$ yang berjarak sama ke titik identifikasi $u,$ yaitu $d(x,u)=d(y,u),$ yang mempunyai representasi sama. Dalam hal $dim(G)=2$, jelas bahwa $dim(G \odot P_n) \geq dim(G).$ % Selanjutnya misalkan $dim(G) \geq 3,$ jika sebanyak $\dim(G)-1$ titik di $W$ diambil dari $G$ dan $P_n$ maka terdapat dua titik yang menjadi anggota himpunan basis di $G$ tetapi tidak menjadi anggota himpunan $W.$ Dua titik ini akan mempunyai representasi yang sama terhadap himpunan $W.$ Karena jika tidak, maka salah satu dari dua titik ini bukan anggota basis dari $G,$ sehingga terjadi kontradiksi. Terbukti setiap subhimpunan dengan $dim(G)-1$ titik bukanlah himpunan pembeda. Oleh karena itu, $dim(G \odot P_n) \geq dim(G).$ % Untuk membuktikan bahwa $dim(G \odot P_n) \leq dim(G)$ adalah dengan membuktikan bahwa banyak titik di himpunan basis $G \odot P_n$ sama dengan banyak titik di himpunan basis $G$. Karena $G$ reguler, maka graf $G \odot P_n$ tidak bergantung pada pemilihan titik identifikasi di $G$. Oleh karena itu, tanpa mengurangi keumuman bukti, dalam hal ini pemilihan titik identifikasi $u \in V(G)$ dilakukan setelah menentukan basis dari graf $G$, dengan beberapa syarat sebagai berikut: \begin{itemize} \item $u$ bukan anggota basis dari $G,$ \item tidak ada titik $z$ di $G$ sedemikian sehingga $r(z|W)=r(u|W)+1$. Dalam hal ini $r(u|W)+1$ didefinisikan sebagai $r(u|W)+1 = (d(u,w_1)+1, d(u,w_2)+1, \ldots, d(u,w_k)+1)$ dengan $W=\{w_1, w_2, \ldots, w_k\}.$ \end{itemize} Dalam hal ini dipilih himpunan pembeda di $G \odot P_n$ sama dengan himpunan pembeda di $G.$ Misalkan $V(G \odot P_n)=V(G) \cup \{v_1, v_2, \ldots, v_{n-1}\}$ dengan $v_{n-1}$ sebagai titik daun. Jelas bahwa setiap titik di $G$ mempunyai representasi yang berbeda. Sedangkan representasi dari setiap titik di $\{v_1, v_2, \ldots, v_{n-1}\}$ juga berbeda karena $r(v_i|W)=r(u|W)+i$ untuk setiap $i=1,2,\ldots,n-1$. Terbukti bahwa $dim(G \odot P_n) = dim(G).$ \end{proof} %--------------------------------------------------------------------------------------------------------------------------------------------------- Pada pembahasan selanjutnya diberikan nilai eksak dimensi metrik dari identifikasi graf $G \odot H$ dengan $G$ dan $H$ graf lingkaran, graf lengkap, atau graf bipartisi lengkap. Pertama diberikan dimensi metrik dari $C_m \odot C_n$. Karena operasi identifikasi merupakan amalgamasi dari dua buah graf, maka dimensi metrik dari identifikasi graf lingkaran telah diberikan oleh Iswadi et al. \cite{iswadi} yang telah mengkaji dimensi metrik dari amalgamasi dari $t$ buah graf lingkaran, yaitu dengan membatasi pada dua graf lingkaran sebarang. Namun demikian pada paper ini, diberikan detail pembuktiannya secara independen. %========================================================================== \begin{corollary} \label{2cycle} Untuk setiap $m$ dan $n$ bilangan bulat positif yang lebih besar dari $2$, maka \[dim(C_m \odot C_n) = \left\{\begin{array}{ll} 3 \qquad & \mbox{jika} ~ m ~\mbox{dan}~n~\mbox{keduanya genap},\\ 2 & \mbox{lainnya.} \end{array}\right.\] \end{corollary} % \begin{proof} Misalkan $V(C_m \odot C_n)=\{c, u_1, \ldots, u_{m-1}, v_1, \ldots, v_{n-1}\}$ dengan titik identifikasi $c$ dan $N(c)=\{u_1, u_{m-1},v_1,v_{n-1}\}$. \begin{itemize} \item Untuk $m$ dan $n$ genap. Pertama akan dibuktikan bahwa setiap subhimpunan dengan dua titik bukanlah himpunan pembeda di $C_m \odot C_n$. Misalkan $W=\{x,y\}$ dengan $x,y \in V(C_m \odot C_n)$. Maka titik $x$ dan $y$ dapat berada pada lingkaran yang sama atau berbeda. Jika $x$ dan $y$ berada pada lingkaran yang sama, misalnya $C_m$, maka titik $v_1$ dan titik $v_{n-1}$ di $C_n$ mempunyai representasi yang sama, yaitu $r(v_1|A)=r(v_{n-1}|A)=(1+d(c,x), 1+d(c,y)).$ Sedangkan untuk $x \in V(C_m)$ dan $y\in V(C_n)$, cukup diperhatikan ketika $x =u_i$ untuk suatu $i=1, 2, \ldots, \frac{m}{2}$ dan $y=v_j$ untuk suatu $j=1, 2, \ldots, \frac{n}{2}.$ % Jika $x=v_\frac{m}{2}$ maka $r(u_1|W)=r(u_\frac{m}{2}|W)=(\frac{m-2}{2},1+d(c,y)).$ % Jika $x=v_i$ dan $y=v_j$ untuk suatu $i\in[1,\frac{m-2}{2}]$ dan $j\in [1,\frac{n-2}{2}]$ maka titik $v_{m-1}$ dan $u_{m-1}$ mempunyai representasi yang sama, yaitu $(1+d(c,x), 1+d(c,y)).$ Dengan demikian $dim(C_m \odot C_n) \geq 3.$ \bigskip Selanjutnya misalkan $W=\{u_{m-1}, v_1, v_{n-1}\}$. Maka $W$ adalah himpunan pembeda dari $C_m \odot C_n$, karena setiap titik di graf $C_m \odot C_n$ mempunyai representasi yang berbeda, yaitu: \[\begin{array}{llll} r(c|W) &= (1,1,1), \\ r(u_i|W) &= \left\{ \begin{array}{ll} (1+i, 1+i, 1+i) & \mbox{untuk}~i=2,3,\ldots, \frac{m-2}{2},\\ (m-1-i, m+1-i,m+1-i)& \mbox{untuk}~ i=\frac{m}{2}, \ldots, m-2,\\ \end{array}\right. \\ r(v_j|W) &= \left\{ \begin{array}{ll} (j+1, j-1,j+1) & \mbox{untuk}~ j=2,3,\ldots, \frac{n-3}{2},\\ (n+1-j, n+1-j,n-1-j) & \mbox{untuk} j=\frac{n-1}{2}, \ldots, n-2. \end{array}\right. \end{array}\] \item Paling banyak satu lingkaran dengan panjang genap. Jelas bahwa $dim(C_m \odot C_n)\geq 2$. Untuk $m$ genap dan $n$ ganjil, misalkan $W_1=\{u_{\frac{m-2}{2}}, v_{\frac{n-1}{2}}\}$. Representasi dari setiap titik di $C_m \odot C_n$ adalah: \[\begin{array}{llll} r(c|W_1) &= (\frac{m-2}{2}, \frac{n-1}{2}), \\ r(u_i|W_1) &= \left\{ \begin{array}{ll} (\frac{m-2}{2}-i, \frac{n-1}{2}+i) & \mbox{untuk}~i=1, 2, \ldots, \frac{m-4}{2},\\ (i-\frac{m-2}{2}, m-i +\frac{n-1}{2})& \mbox{untuk}~ i=\frac{m}{2}, \ldots, m-1,\\ \end{array}\right. \\ r(v_j|W_1) &= \left\{ \begin{array}{ll} (j+\frac{m-2}{2}, \frac{n-1}{2}-j) & \mbox{untuk}~ j=1, 2,\ldots, \frac{n-3}{2},\\ (n-j+\frac{m-2}{2}, j-\frac{n-1}{2}) & \mbox{untuk}~ j=\frac{n+1}{2}, \ldots, n-1. \end{array}\right. \end{array}\] \noindent Sedangkan untuk $m$ dan $n$ ganjil, pilih $W_2=\{u_{\frac{m-1}{2}}, v_{1}\}$. Representasi dari setiap titik di $C_m \odot C_n$ adalah: \[\begin{array}{llll} r(c|W_2) &= (\frac{m-1}{2}, 1), \\ r(u_i|W_2) &= \left\{ \begin{array}{ll} (\frac{m-1}{2}-i, 1+i) & \mbox{untuk}~i=1, 2, \ldots, \frac{m-3}{2},\\ (i-\frac{m-1}{2}, m-i +1)& \mbox{untuk}~ i=\frac{m+1}{2}, \ldots, m-1,\\ \end{array}\right. \\ r(v_j|W_2) &= \left\{ \begin{array}{ll} (\frac{m-1}{2}+j, j-1) & \mbox{untuk}~ j=2, 3,\ldots, \frac{n+1}{2},\\ (n-j+\frac{m-1}{2}, n-j+1) & \mbox{untuk}~ j=\frac{n+3}{2}, \ldots, n-1. \end{array}\right. \end{array}\] \end{itemize} \end{proof} \noindent Sebagai gambaran dimensi metrik pada graf hasil identifikasi dua graf lingkaran, dapat dilihat pada Gambar \ref{2cy}. \begin{figure}[htbp] \begin{center} \includegraphics[width=5cm]{A/2cc1} \includegraphics[width=5cm]{A/2cc2} \caption{Dimensi metrik dari graf hasil identifikasi dua graf lingkaran} % $C_{14}[(4,P_2); (1,2,3)].$} \label{2cy} \end{center} \end{figure} %========================================================================== Dimensi metrik dari graf hasil identifikasi graf lengkap memenuhi batas bawah yang diberikan oleh Poisson dan Zhang \cite{poisson}. \bigskip \begin{theorem} \label{2complete} Untuk setiap $m$ dan $n$ bilangan bulat positif yang lebih besar dari $3,$ maka \[dim(K_m \odot K_n) = m+n-4.\] \end{theorem} \begin{proof} Misalkan $V(K_m \odot K_n)=\{c, u_1, \ldots, u_{m-1}, v_1, \ldots, v_{n-1}\}$ dengan titik identifikasi $c$. %Tentu saja titik identifikasi $c$ berjarak satu dengan setiap titik di $K_m \odot K_n$ dan setiap titik di $K_m$ berjarak dua dengan setiap titik di $K_n$. Dengan demikian terdapat tepat tiga buah titik yang tidak menjadi anggota himpunan basis $W$ dari $K_m \odot K_n$, yaitu titik identifikasi $c$, tepat sebuah titik sebarang di $K_m$ dan tepat sebuah titik sebarang di $K_n$. % %Karena jika terdapat lebih dari satu titik di $K_m$ yang tidak menjadi anggota himpunan basis $W$, misalkan titik $u_r$ dan $u_s$ di $W$ untuk suatu $u,r \in [1,m-1]$ maka kedua titik ini akan mempunyai representasi yang sama, yaitu $(1,1,\ldots, 1, 2,2, \ldots, 2)$. Hal yang sama terjadi jika terdapat lebih dari satu titik di graf lengkap $K_n$ yang tidak menjadi anggota himpunan $W$, yaitu titik-titik tersebut mempunyai representasi yang sama yaitu $(2,2, \ldots, 2, 1,1, \ldots, 1)$. Berdasarkan Teorema \ref{zhang} diperoleh $dim(K_m \odot K_n) \geq (m-1)+(n-1)-2 = m+n-4.$ Untuk membuktikan bahwa $dim(K_m \odot K_n) \leq m+n-4$, untuk setiap bilangan bulat $m,n \geq 3,$ pilih $W=V(K_m \odot K_n) \backslash \{c, u_1, v_1\}.$ Jelas bahwa $W$ adalah himpunan pembeda, karena setiap titik di $K_m \odot K_n$ mempunyai representasi yang berbeda. Adapun representasi dari titik yang bukan anggota basis $W$ adalah: %\[\begin{array}{llll} $r(c|W) = (\underbrace{1,\ldots, 1}_{m+n-4}),$ $r(u_{1}|W) = (\underbrace{1,\ldots,1}_{m-2},\underbrace{2, \ldots, 2}_{n-2}),$ dan $r(v_{1}|W) = (3,\underbrace{2,\ldots,2}_{m-2},\underbrace{1, \ldots, 1}_{n-2}).$ %\end{array}\] \end{proof} %\bigskip \noindent Pada Gambar \ref{cc} diberikan dimensi metrik dari graf hasil identifikasi $K_5$ dan $K_9$ dengan tiga buah titik berwarna putih bukan anggota basis dari graf $K_5 \odot K_9$. %\begin{figure} %\begin{center} %\includegraphics[width=4cm]{A/2kn} %\caption{$dim(K_5 \odot K_9)=10$} % $C_{14}[(4,P_2); (1,2,3)].$} %\label{2kn} %\end{center} %\end{figure} \bigskip %========================================================================== Dimensi metrik dari graf hasil identifikasi graf lengkap dan graf lingkaran, selain tidak bergantung dari ganjil atau genapnya banyak titik di lingkaran, juga memenuhi batas bawah yang diberikan oleh Poisson dan Zhang \cite{poisson} pada Teorema \ref{zhang}, sebagaimana dibuktikan pada teorema berikut ini. \begin{theorem} \label{2cc} Untuk setiap $m$ dan $n$ bilangan bulat positif yang lebih besar dari $3$, maka \[dim(K_m \odot C_n) = m-1.\] \end{theorem} \begin{proof} Misalkan $V(K_m \odot C_n)=\{c, u_1, \ldots, u_{m-1}, v_1, \ldots, v_{n-1}\}$ dengan titik identifikasi $c$. %Tentu saja titik identifikasi $c$ berderajat $m+1$ dan $d(u_i, v_j)=1+d(c, v_j)$. Pertama akan dibuktikan bahwa setiap himpunan $W$ dengan $m-2$ titik, bukan merupakan himpunan pembeda. Jika $m-2$ titik diambil dari graf lengkap $K_m$, maka titik $v_1$ dan $v_{n-1}$ di graf lingkaran $C_n$ mempunyai representasi yang sama, yaitu $(2,2,\ldots,2)$. % Berdasarkan Teorema \ref{zhang} diperoleh $dim(K_m \odot C_n) \geq (m-1)+2-2=m-1.$ %Jika $m-2$ titik diambil dari graf lengkap $K_m$ dan termasuk titik identifikasi, maka dua titik sisa di graf lengkap $K_m$ mempunyai representasi yang sama, yaitu $(1,1,\ldots,1)$. % %Jika $m-2$ titik diambil dari graf lengkap $K_m$ dan graf lingkaran $C_n$, misalkan titik $v \in V(C_n)$ adalah anggota $W$, maka ada dua titik di graf lengkap $K_m$, sebut $x$ dan $y$ dengan $\deg(x)=\deg(y)$, tidak masuk dalam himpunan $W$ sehingga titik $x$ dan $y$ mempunyai representasi yang sama, yaitu $(1,1,\ldots,1, 1+d(c,v))$. % %Dengan demikian hanya boleh ada tepat sebuah titik di $K_m$ (bukan titik identifikasi $c$) yang bukan anggota $W$. Oleh karena itu $dim(K_m \odot C_n) > m-2$. Selanjutnya jika diambil subhimpunan dengan $m-1$ titik, yaitu $W=\{v_1, v_2, \ldots, v_{m-2}, u_1\}$, maka $W$ adalah himpunan pembeda, karena representasi setiap titik di $K_m \odot C_n$ berbeda semua, yaitu: % \[\begin{array}{llll} r(c|W) &= (\underbrace{1,\ldots, 1}_{m-1}), \\ r(v_{m-1}|W) &= (\underbrace{1,\ldots,1}_{m-2},2), \\ r(v_j|W) &= \left\{ \begin{array}{ll} (\underbrace{j+1, \ldots, j+1}_{m-2}, j-1) & \mbox{untuk}~ j=2, 3,\ldots, \frac{n}{2},\\ (\underbrace{n-j+1, \ldots, n-j+1}_{m-1}) & \mbox{untuk}~ j=\frac{n+2}{2}, \ldots, n-1. \end{array}\right. \end{array}\] \end{proof} \noindent Pada Gambar \ref{cc} diberikan dimensi metrik dari graf hasil identifikasi $K_6$ dan $C_8$, $dim(K_6 \odot C_8)=5$ dengan tiga buah titik berwarna putih adalah titik-titik yang tidak menjadi anggota basis dari graf $K_6 \odot C_8$. \begin{figure}[htbp] \begin{center} \includegraphics[width=12cm]{A/2kck} %\includegraphics[width=6cm]{A/2kk} \caption{Dimensi metrik dari graf $K_6 \odot C_8$ dan $K_5 \odot K_9$} % $C_{14}[(4,P_2); (1,2,3)].$} \label{cc} \end{center} \end{figure} \bigskip %========================================================================== Selanjutnya diberikan dimensi metrik dari graf hasil identifikasi dari graf bipartisi lengkap dengan graf lengkap atau graf lingkaran. Keduanya memenuhi batas bawah yang diberikan oleh Poisson dan Zhang \cite{poisson} pada Teorema \ref{zhang}, sebagaimana dibuktikan pada teorema berikut ini. \begin{theorem} \label{2cb} Misalkan $m,n \geq 2$ dan $s \geq 3$ adalah bilangan bulat positif. Maka \begin{enumerate} \item[$(i)$] $dim(K_{m,n} \odot C_s) = m+n-2,$ \item[$(ii)$] $dim(K_{m,n} \odot K_s) = m+n+s-5.$ \end{enumerate} \end{theorem} \begin{proof} Berdasarkan Teorema \ref{zhang} didapatkan $dim(K_{m,n} \odot C_s) \geq m+n-2$ dan $dim(K_{m,n} \odot K_s) \geq m+n+s-5.$ Unruk membuktikan batas atas dari keduanya, misalkan $V(K_{m,n} \odot C_s)=V(K_{m,n} \odot K_s)=\{c, u_i, v_j, x_k|i\in[1,m], j \in [1,n-1], k\in[1, s-1]\}.$ %Pertama akan ditunjukkan bahwa setiap subhimpunan $W$ dengan $m+n-3$ titik di $K_{m,n} \odot C_s$ bukan himpunan pembeda. Jika paling banyak satu titik dari $m+n-3$ titik diambil dari graf $C_{s}$ maka ada dua titik di $K_{m,n}$ yang tidak di $W$ ada dalam partisi yang sama. Dua titik ini mempunyai representasi yang sama. % %Jika semua $m+n-3$ titik diambil dari graf $C_{s}$ maka dua titik di $K_{m,n}$ yang ada dalam partisi yang sama, mempunyai representasi yang sama. % %Dengan demikian $dim(K_{m,n} \odot C_s) \geq m+n-2.$ % Pilih $W_1=\{x_1, u_i, v_j ~|~\mbox{dengan}~i \in [1,m-1]~ \mbox{dan}~j \in [1, n-2]\}$ dan $W_2=V(K_{m,n} \odot K_s) \backslash \{c, u_1, v_1, x_1\}.$ Representasi setiap titik di $V(K_{m,n} \odot C_s) \backslash W_1$ adalah sebagai berikut. % \[\begin{array}{llll} r(c|W_1) &= (1,\underbrace{1,\ldots, 1}_{m-1}, \underbrace{2, \ldots, 2}_{n-2}), \\ r(u_{m}|W_1) &= (2,\underbrace{2,\ldots,2}_{m-1},\underbrace{1, \ldots, 1}_{n-2}), \\ r(v_{n-1}|W_1) &= (3,\underbrace{1,\ldots,1}_{m-1},\underbrace{2, \ldots, 2}_{n-2}), \\ r(x_k|W_1) &= \left\{ \begin{array}{ll} (k-1, \underbrace{k+1, \ldots, k+1}_{m-1}, \underbrace{k+2, \ldots, k+2}_{n-2}) & \mbox{untuk}~ k \in\left[2, \lceil\frac{s-1}{2}\rceil\right],\\ (k-1, \underbrace{a, \ldots, a}_{m-1}, \underbrace{a+1,\ldots, a+1}_{n-2}) & \mbox{untuk}~ k=\frac{s+1}{2}, s~\mbox{ganjil,}\\ (a, \underbrace{a, \ldots, a}_{m-1},\underbrace{ a+1, \ldots, a+1}_{n-2}) & \mbox{untuk}~ k\in \left[\lceil\frac{s+2}{2}\rceil, s-1\right]. \end{array}\right. \end{array}\] % dengan $a=s-k+1$. % Sedangkan representasi setiap titik di $V(K_{m,n} \odot K_s) \backslash W_2$ adalah sebagai berikut. % \[\begin{array}{lllll} r(c|W_2) &= (\underbrace{1, \ldots, 1}_{m-1},\underbrace{2,\ldots, 2}_{n-2}, \underbrace{1, \ldots, 1}_{s-2}), ~& r(u_{1}|W_2) &= (\underbrace{2, \ldots, 2}_{m-1},\underbrace{1,\ldots,1}_{n-2},\underbrace{2, \ldots, 2}_{s-2}), \\ r(v_{1}|W_2) &= (\underbrace{1, \ldots, 1}_{m-1},\underbrace{2,\ldots,2}_{n-2},\underbrace{3, \ldots, 3}_{s-2}), ~& r(x_1|W_2) &= (\underbrace{2, \ldots, 2}_{m-1}, \underbrace{3, \ldots, 3}_{n-2}, \underbrace{1, \ldots, 1}_{s-2}). \end{array}\] % Karena setiap titik mempunyai representasi yang berbeda maka $W_1$ adalah himpunan pembeda di $K_{m,n} \odot C_s,$ sedangakan $W_2$ adalah himpunan pembeda di $K_{m,n} \odot K_s.$ \end{proof} \noindent Pada Gambar \ref{bck} diberikan dimensi metrik dari graf $K_{5, 3} \odot C_9$, dan $(K_{3,5} \odot K_9).$ Penulisan $K_{3,5}$ menjadi $K_{5,3}$ atau sebaliknya, dimaksudkan untuk mempermudah dalam merumuskan representasi titik-titiknya, karena dalam hal ini dimensi metriknya tidak bergantung dari pemilihan titik identifikasi pada graf bipartisi lengkap, apakah pada titik berderajat $m$ atau $n.$ Basis dari graf $K_{5, 3} \odot C_9$ dan $(K_{3,5} \odot K_9)$ pada Gambar \ref{bck} digambarkan sebagai titik-titik yang berwarna. % \begin{figure}[htbp] \begin{center} %\includegraphics[width=5cm]{A/2kn} \includegraphics[width=6cm]{A/bkc} \includegraphics[width=6cm]{A/bkk} \caption{Dimensi metrik dari graf $K_{5,3} \odot C_9$ dan $K_{3,5} \odot K_9$} % $C_{14}[(4,P_2); (1,2,3)].$} \label{bck} \end{center} \end{figure} %========================================================================== %\begin{theorem} \label{2kb} %Untuk setiap $m,n \geq 2$ dan $s \geq 3$ bilangan bulat positif, %\[dim(K_{m,n} \odot K_s) = m+n+s-5.\] %\end{theorem} %\noindent Pada Gambar \ref{bck} diberikan dimensi metrik dari graf hasil identifikasi $K_6$ dan $C_8$, $dim(K_6 \odot C_8)=5$ dengan tiga buah titik berwarna putih bukan anggota basis dari graf $K_6 \odot C_8$. %\begin{figure}[htbp] %\begin{center} %\includegraphics[width=5cm]{A/2kn} %\includegraphics[width=8cm]{A/bkk} %\caption{Graf hasil identifikasi dua graf lengkap $K_5 \odot K_9$ dengan himpunan basisnya} % $C_{14}[(4,P_2); (1,2,3)].$} %\label{bck} %\end{center} %\end{figure} %========================================================================== % \section{Kesimpulan} Beberapa hasil yang diperoleh terkait dimensi metrik dari graf hasil identifikasi adalah sebagai berikut: \begin{itemize} \item Misalkan $G$ graf reguler dan $v$ titik daun pada graf lintasan $P_n,$ maka dimensi metrik dari graf hasil identifikasi $G$ dengan $P_n$ pada titik $v$ adalah tetap, yaitu $dim(G \odot P_n)=dim(G).$ \item Beberapa kelas graf hasil identifikasi yang dimensi metriknya tepat sama dengan batas bawah dari Poisson dan Zhang \cite{poisson} pada Teorema \ref{zhang}, yaitu $dim(G \odot H)=dim(G)+dim(H)-2,$ adalah graf $C_{2m+1} \odot C_n,$ $K_m \odot K_n,$ $K_m \odot C_n,$ $K_{m,n} \odot C_s,$ dan $K_{m,n} \odot K_s,$ untuk setiap $m, n,$ dan $s$ bilangan bulat positif. \end{itemize} Masih terbuka kajian dimensi metrik terkait dengan graf hasil identifikasi. Beberapa diantaranya adalah: \begin{itemize} \item Tentukan dimensi metrik dari $G \odot P_n$ jika titik identifikasi pada graf lintasan $P_n$ selain titik daun; dan juga jika $G$ tidak reguler! \item Karakterisasi kelas-kelas graf $G$ dan $H$ yang dimensi metriknya tepat sama dengan hasil Poisson dan Zhang \cite{poisson} pada Teorema \ref{zhang}, yaitu $dim(G \odot H)=dim(G)+dim(H)-2.$ \end{itemize} %---------------------------------------------------------------------------------------------------------------------------------------------------- \begin{thebibliography}{99} \bibitem{Akhter} Akhter, S. and Farooq, R., (2019), Metric Dimension of Fullerene Graphs, {\em Electronic Journal of Graph Theory and Applications}, {\bf 7(1)}: 91--103. \bibitem{anggraeni} Angraini, F., Welyyanti, D., Syafruddin, (2018), Dimensi Metrik dan Dimensi Partisi dari Graf Tangga Segitiga $Tr_n$ untuk $n = 2, 3$, {\em Jurnal Matematika UNAND} {\bf 7(2)}: 46-52 \bibitem{Bailey} Bailey, R.F., C\'{a}ceres, J., Garijo, D., Gonz\'{a}lez, A., M\'{a}rquez, A., Meagher, K., and Puertas, M.L., (2013), Resolving sets for Johnson and Kneser graphs, {\em European Journal of Combinatorics}, {\bf 34}: 736--751. %\bibitem{Chappell} %Chappell, G., Gimbel, J., and Hartman, C., (2008), Bounds on the metric and partition dimensions of a graph, {Ars combinatoria}, {88}, pp. 349-366. \bibitem{Chartrand} Chartrand, G., Eroh, L., Johnson, M. A., and Oellermann, O. R., (2000), Resolvability in graph and the metric dimension of graph, {\em Discrete Applied Mathematics}, {\bf 105}: 99--113. \bibitem{Dudenko} Dudenko, M. and Oliynyk, B., (2017), On unicyclic graphs of metric dimension 2, {\em Algebra and Discrete Mathematics}, {\bf 23(2)}: 216--222. \bibitem{Dudenko18} Dudenko, M. and Oliynyk, B., (2018), On unicyclic graphs of metric dimension 2 with vertices of degree 4, {\em Algebra and Discrete Mathematics}, {\bf 26(2)}: 256--269. \bibitem{fitri} Fitriani, F., (2021), Dimensi Metrik penghapusan satu simpul graf dual antiprisma, {\em Jurnal Matematika UNAND } {\bf 10(3)}: 379—384. \bibitem{febri} Febrianti, F., Yulianti, L., Narwen, (2019), Dimensi Metrik Pada Graf Amalgamasi Tangga Segitiga Diperumum Homogen, {\em Jurnal Matematika UNAND} {\bf 8(1)}: 84 – 90. \bibitem{Harary} Harary, F. and Melter, R. A., (1976), On the metric dimension of a graph, {\em Ars Combinatoria}, {\bf 2}: 191--195. \bibitem{Imran13} Imran, M., Bashir, F., Baig, A. Q., Bokhary, S. A. U. H., Riasat, A., and Tomescu, I., (2013), On metric dimension of flower graph $f_{n\times m}$ and convex polytopes, {\em Utilitas Mathematica}, {\bf 92}: 389--409. \bibitem{iswadi} Iswadi, H., Baskoro, E.T., Salman, A.N.M., Simanjuntak, R., (2010), The Metric Dimension of Amalgamation of Cycles, {\em Far East Journal of Mathematical Sciences (FJMS)} {\bf 41(1)}: 19--31. \bibitem{Marinda}Marinda, D., Syafruddin, (2015), Dimensi Metrik dari Graf Naga $T_{n,m}$, {\em Jurnal Matematika UNAND} {\bf 4(3)}: 25-30. \bibitem{mayora} Mayora, C., Narwen, Welyyanti, D., (2018) Dimensi Metrik dari Graf Spinner $(C_3 \times P_2) \odot \bar{K_n}$ untuk $n = 1$, {\em Jurnal Matematika UNAND} {\bf 7(4)}: 1--6. \bibitem{poisson} Poisson, C. and Zhang, P., (2002), The metric dimension of unicyclic graphs, {\it J. Combin. Math. Combin. Comput.} {\bf 40}: 17--32. \bibitem{pratama} Pratama, R.A., Narwen, Welyyanti, D., (2019), Dimensi Metrik pada Graf $R_n(q; r)m$ {\em Jurnal Matematika UNAND} {\bf 8(1)}: 260—266. \bibitem{putra} Putra, R.N.S., Yulianti, L., Sy, S., (2018), Dimensi Metrik dari Graf $W_n + C_n$ untuk $n \in \{3, 4\}$, {\em Jurnal Matematika UNAND} {\bf 7(2)}: 165-169 \bibitem{putrif} Putri, A.F., Yulianti, L., Rudianto, B., (2019), Dimensi Metrik dari Graf $Amal(Tr_n, v)_m$ untuk $n = 5$ dan $m = 3$, {\em Jurnal Matematika UNAND} {\bf 8(1)}: 1--8. \bibitem{putrih} Putri, A.H., Yulianti, L., Welyyanti, D., (2019), Dimensi Metrik Dari Graf Buckminsterfullerene {\em Jurnal Matematika UNAND} {\bf 8(4)}: 91--100. \bibitem{pdwi} Purwati, D., Rudianto, B., (2015), Dimensi Metrik Graf Hasilkali Kartesius Dua Lintasan $(P_n \times P_m)$ Korona Graf Lengkap $K_1$, {\em Jurnal Matematika UNAND} {\bf 4(4)}: 28-33. \bibitem{rahma} Rahmadani, F., Syafruddin, (2015), Dimensi Metrik dari Graf Barbel $B_{2n}$, $n \geq 3$, {\em Jurnal Matematika UNAND} {\bf 4(2)}: 89-94. \bibitem{rahmi} Rahmi, N.M., Zulakmal, (2016), Dimensi Metrik dari $(K_n \times P_m) \odot K_1$, {\em Jurnal Matematika UNAND} {\bf 5(1)}: 90-95. \bibitem{riyan} Riyandho, R., Narwen, Efendi, (2018), Dimensi Metrik Graf Kincir Pola $K_1 + mK_4$, {\em Jurnal Matematika UNAND} {\bf 7(3)}: 149--153. \bibitem{saputro} Saputro, S.W., Mardiana, N., Purwasih, I.A., (2017), The Metric Dimension of Comb Product Graphs {\em Matematicki Vesnik} {\bf 69(4)}: 248–258 \bibitem{Siddiq15} Siddiqui, H. M. A. and Imran, M., (2015), Computation of metric dimension and partition dimension of Nanotubes, \textit{Journal of Computational and Theoretical Nanoscience}, {\bf 12}: 199--203. \bibitem{Siddiq14} Siddiqui, H. M. A. and Imran, M., (2014), Computing metric and partition dimension of 2- Dimensional lattices of certain Nanotubes, {\em Journal of Computational and Theoretical Nanoscience}, {\bf 11}: 2419--2423. \bibitem{Slater75} Slater, P. J., (1975), Leaves of trees, {\em Congressus Numerantium 14 (1975) 549559. Proceeding 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing}. \end{thebibliography} \end{document} %==========================================================================