Earticle

초록

영어

For simple undirected graph G = ( V, E ) , L(2,1)-coloring of G is a nonnegative real-valued function f : V → [0, 1, ⋯ , k] such that whenever vertices x and y are adjacent in G then ㅣf(x) - f(y) ㅣ≥ 2 and whenever the distance between x and y is 2, ㅣf(x) - f(y) ㅣ≥ 1. For a given L (2,1)-coloring c of graph G , the c-span is λ(c) = max{ㅣc(u) - c(v) ㅣㅣ u, v ∈ V }. L(2,1)-coloring number λ(G) = min λ(c) } where the minimum is taken over all L (2,1)-coloring c of graph G. In this paper, based on Harary’s Theorem, we use Tabu Search to figure out the existence of Hamiltonian Path in a complementary graph and confirmed that if λ(G) is equal to n ( = ㅣVㅣ).    .

한국어

단순 무방향 그래프 G 의 L(2,1)-coloring은 d(u,v) 가 두 정점 사이의 거리일 때 두 가지 조건 (1) d(x,y) = 1 라면 ㅣf(x) - f(y) ㅣ≥ 2, (2) d(x,y) = 2 라면 ㅣf(x) - f(y) ㅣ≥ 1 을 만족하는 함수 f : V → [0, 1, ⋯ , k] 를 정의하는 것이다. 임의의 L (2,1)-coloring c 에 대하여 G 의 c-span 은 λ(c) = max{ㅣc(u) - c(v) ㅣㅣ u, v ∈ V } 이며, L (2,1)-coloring number 인 λ(G) 는 모든 가능한 c 에 대하여 λ(G) = min λ(c) } 로 정의된다. 본 논문에서는 Harary의 정리에 기반하여 지름이 2인 그래프에 대하여 여그래프에 해밀턴 경로의 존재여부를 Tabu Search를 사용해 판단하고 이를 통해 λ(G) 가 n ( = ㅣVㅣ)과 같음을 분석한다.

목차

요약
Abstract
1. 서론
2. 연구방법
2.1 Harary의 정리
2.2 Tabu Search
3. 실험 및 결과
4. 결론
REFERENCES

키워드

L (2 1)-coloring L (2 1)-coloring number 지름이 2인 그래프 여그래프 Tabu Search L (2 1)-coloring L (2 1)-coloring number Graph with diameter 2 Complement graph Tabu Search

저자

• 김소정 [ SoJeong Kim | 공주대학교 응용수학과 석사과정 ]
• 김찬수 [ ChanSoo Kim | 공주대학교 응용수학과 교수 ]
• 한근희 [ KeunHee Han | 공주대학교 응용수학과 교수 ] Corresponding Author

참고문헌

발행기관

간행물