RESOLVABILITY OF GRAPHS BASED ON REPRESENTATIONS AND MULTIREPRESENTATIONS

Abstract

Let G be a connected graph and let W={w1,w2,...,wk} be an ordered set of vertices of G. For the vertex v of G, the representation of v with respect to W is the k-vector r(v|W)=(d(v,w1),d(v,w2),...,d(v,wk)), where d(v,wi) for i=1,2,...,k is the distance between v and wi in G. An ordered set W is a connected local resolving set of G if the representations of every two adjacent vertices of G with respect to W are distinct and the induced subgraph <W> of G is connected. A connected local resolving set of G with minimum cardinality is a minimum connected local resolving set or a connected local basis of G, and this cardinality is the connected local dimension of G. For a set W={w1,w2,...,wk} of vertices of G, the multirepresentation of vertex v of G with respect to W is the k-multiset mr(v|W)={d(v,w1),d(v,w2),...,d(v,wk)}. The set W is a multiresolving set of G if the multirepresentations of every two vertices of G with respect to W are distinct. A multiresolving set of G with minimum cardinality is a minimum multiresolving set or a multibasis of G, and this cardinality is the multidimension of G. In this work, we studied the connected local dimensions of some well-known graphs and the relationships between connected local bases and local bases in a connected graph, and some realization results. Next, the relationship between the elements in multirepresentations of vertices that belonged to the same multisimilar class was investigated. Moreover, the caterpillars were characterized with multidimension 3 and studying the multiresolving sets of symmetric caterpillars.

กำหนดให้ G เป็นกราฟเชื่อมโยง และให้ W={w1,w2,...,wk} เป็นเซตอันดับของจุดในกราฟ G สำหรับจุด v ในกราฟ G ตัวแทนของจุด v เทียบกับเซต W คือ k-เวกเตอร์ r(v|W)=(d(v,w1),d(v,w2),...,d(v,wk)) เมื่อ d(v,wi) สำหรับ i=1,2,...,k คือ ระยะทางระหว่างจุด v และจุด wi ในกราฟ G เราเรียกเซตอันดับ W ว่าเซตจำแนกเฉพาะที่อย่างเชื่อมโยงของกราฟ G ถ้าตัวแทนของสองจุดใดๆ ที่ประชิดกันในกราฟ G นั้นแตกต่างกัน และกราฟย่อยชักนำ <W> ของกราฟ G เป็นกราฟเชื่อมโยง เราเรียกเซตจำแนกเฉพาะที่อย่างเชื่อมโยงของกราฟ G ซึ่งมีสมาชิกน้อยที่สุดว่า เซตจำแนกเฉพาะที่อย่างเชื่อมโยงน้อยสุด หรือ ฐานเฉพาะที่อย่างเชื่อมโยง ของกราฟ G และจำนวนสมาชิกในฐานเฉพาะที่อย่างเชื่อมโยงของกราฟ G คือ มิติเฉพาะที่อย่างเชื่อมโยงของกราฟ G สำหรับเซต W={w1,w2,...,wk} ของจุดในกราฟ G ตัวแทนเชิงซ้ำของจุด v เทียบกับเซต W คือ k-เซตเชิงซ้ำ mr(v|W)={d(v,w1),d(v,w2),...,d(v,wk)} เราเรียกเซต W ว่าเซตจำแนกเชิงซ้ำของกราฟ G ถ้าตัวแทนเชิงซ้ำของสองจุดใดๆ ในกราฟ G นั้นแตกต่างกัน เราเรียกเซตจำแนกเชิงซ้ำของกราฟ G ซึ่งมีสมาชิกน้อยที่สุดว่า เซตจำแนกเชิงซ้ำน้อยสุด หรือ ฐานเชิงซ้ำ ของกราฟ G และจำนวนสมาชิกในฐานเชิงซ้ำของกราฟ G คือ มิติเชิงซ้ำของกราฟ G ในปริญญานิพนธ์นี้ สิ่งแรกที่เราได้ศึกษาคือ มิติเฉพาะที่อย่างเชื่อมโยงของกราฟซึ่งเป็นที่รู้จักโดยทั่วไป และความสัมพันธ์ระหว่าง ฐานเฉพาะที่อย่างเชื่อมโยงกับฐานเฉพาะที่ของกราฟเชื่อมโยง และการมีอยู่ของกราฟ ต่อมาเราได้ศึกษาเกี่ยวกับความสัมพันธ์ระหว่างสมาชิกในตัวแทนเชิงซ้ำของจุดที่อยู่ในชั้นเสมือนเชิงซ้ำเดียวกัน นอกจากนี้เราได้หาลักษณะเฉพาะของกราฟหนอนผีเสื้อที่มีมิติเชิงซ้ำเป็น 3 และยังได้ศึกษาเซตจำแนกเชิงซ้ำของกราฟหนอนผีเสื้อเชิงสมมาตร