Local equivalence of directed graphs and monadic second-order logic = 유향그래프의 국지적 동등과 단항 이차 논리

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 205
  • Download : 0
For a simple directed graph $\It{F}$ if there is an arc from $\It{x}$ to $\It{y}$ for a pair $\It{x}$, $\It{y}$ of distinct vertices, then we call $\It{x}$ an $\It{inneighbor}$ of $\It{y}$ and conversely $\It{y}$ an $\It{outneighbor}$ of $\It{x}$. To locally complement F at a vertex v is for each inneighbor x and outneighbor y of v, to delete the arc (x, y) if there is an arc from $\It{x}$ to $\It{y}$, or to add an arc from x to y otherwise. We say that a directed graph $\It{F}$ is $\It{locally equvalent}$ to another directed graph $\It{H}$ if $\It{H}$ is obtained from F by successive local complementations. Furthermore a directed graph $\It{H}$ is a $\It{vertex-minor}$ of F if H can be obtained by applying a sequence of local complementations and deletions of vertices to $\It{F}$. A. Bouchet introduced Eulerian systems which are related to directed graphs and shows that a pair of directed graphs $\It{F}$, H have same Eulerian system if and only if $\It{H}$ is locally equivalent to F. We show that vertex-minor relation can be expressed in modulo-2 counting monadic second-order logic. This generalizes known properties of local complementations and vertex-minors of undirected graphs to directed graphs.
Advisors
Oum, Sang-Ilresearcher엄상일researcher
Description
한국과학기술원 : 수리과학과,
Publisher
한국과학기술원
Issue Date
2010
Identifier
455185/325007  / 020084129
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 수리과학과, 2010.08, [ iii, 20 p. ]

Keywords

vertex-minor; monadic second-order logic; local equivalence; directed graphs; eulerian systems; 오일러리안 시스템; 꼭지점마이너; 단항 이차 논리; 국지적 동등; 유향그래프

URI
http://hdl.handle.net/10203/42235
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=455185&flag=dissertation
Appears in Collection
MA-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0