컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0509 |
|---|---|
| 분류(Section) | Poster Session |
| 분과(Session) | Combinatorics / Graph Theory / Cryptography / Coding Theory (SS-05) |
| 영문제목 (Title(Eng.)) |
[CANCELED] Partition dimension for a subdivision of homogeneous caterpillars and upper bound of subdivision of trees |
| 저자(Author(s)) |
Amrullah1, Edy Tri Baskoro2, Saladin Uttunggadewa3, Rinovia Simanjutak4 Institut Teknologi Bandung1, -2, -3, -4 |
| 초록본문(Abstract) | The concept of a graph partition dimension was introduced by Chartrand et.al, (1998). Let $G(V,E)$ be a connected graph. For every $v\in V(G)$ and $S\subseteq V(G)$, define the \emph{distance} from $v$ to $S$ is $d(v,S)=min\{d(v,w)|w\in S\}$. Let $\Pi=\{S_1,S_2,...,S_k\}$ be a partition of $V(G)$. The \emph{representation of vertex} $v$ with respect to $\Pi$ is defined as $r(v|\Pi)=(d(v,S_1),d(v,S_2),...,d(v,S_k))$. The partition $\Pi$ is called a \emph{resolving partition} of $G$ if all representations of the vertices are distinct. The \emph{partition dimension} of a graph $G$ can be defined as the cardinality of a minimum resolving partition $\Pi$ of $G$. \newline Now, define a \emph{subdivision graph} $S(G(k))$ on one edge in $k$ times of graph $G$ is graph obtained from $G$ with replacing an edge $ab$ by a path $(a,x_1,x_2,\cdots, x_k,b)$ where for all $x_i\not\in G$. In this paper, we determine of partition dimension of $S(G(k))$ with $G \simeq C(m;r)$ be a homogeneous caterpillar graph and upper bound of $S(G(k))$ with $G$ is tree. We have conclude that upper bound of partition dimension is $pd(S(G(k))\leq pd(G)+1$ where G is tree, and $pd(S(G(k))=pd(G)$ where $G=C(m;r)$ for all value of $m,r$ and $k$ except for subdivision on non pendant edge with $(m=3,r=3)$, $(m=2,r=3,k=4)$ and for subdivision on pendant edge with $m=r+1$. |
| 분류기호 (MSC number(s)) |
05C12, 05C15 |
| 키워드(Keyword(s)) | partition dimension, tree, caterpillar graph |
| 강연 형태 (Language of Session (Talk)) |
English |