DIKUL - logo
(UL)
  • On graphs with complete multipartite ▫$\mu$▫-graphs
    Jurišić, Aleksandar ; Munemasa, Akihiro ; Tagami, Yuki
    Jurišić in Koolen sta predlagala študijo ▫$1$▫-homogenih razdaljno-regularnih grafov, katerih ▫$\mu$▫-grafi (tj. podgrafi, ki so inducirani s skupnimi sosedi dveh vozlišč na razdalji ▫$2$▫) so polni ... večdelni. Na seznamu primerov so med med drugim Johnsonov graf J▫$(8,4)$▫, polovična ▫$8$▫-kocka, znani posplošeni četverokotnik ▫$(4,2)$▫, Meixnerjeva antipodna razdaljno-regularna grafa premera ▫$4$▫ in Pattersonov graf. V članku študiramo splošnejše grafe, katerih ▫$\mu$▫-grafi so polni večdelni in za katere obstaja presečno število ▫$\alpha$▫. Slednje pomeni, da za trojico ▫$(x,y,z)$▫ vozlišč grafa ▫$\Gamma$▫, kjer sta ▫$x$▫ in ▫$y$▫ sosednji, ▫$z$▫ pa je na razdalji ▫$2$▫ od obeh, število ▫$\alpha(x,y,z)$▫ skupnih sosedov od ▫$x$▫, ▫$y$▫ in ▫$z$▫, ni odvisno od izbire trojice. To lastnost imajo ▫$1$▫-homogeni grafi. Naj bo ▫$K_{t \times n}$▫ poln večdelen graf s ▫$t$▫ deli, od katerih je vsak del ▫$n$▫-koklika. Če so v grafu ▫$\Gamma$▫ vsi ▫$\mu$▫-grafi izomorfni ▫$K_{t \times n}$▫ ter obstaja presečno število ▫$\alpha$▫, potem za ▫$\alpha \ge 2$▫ dokažemo ▫$\alpha=t$▫, kot pravi domneva Jurišića in Koolna. Dokažemo tudi ▫$t \le 4$▫. Enakost velja le v primeru, ko je ▫$\Gamma$▫ natanko določen razdaljno-regularni graf ▫$3.O_7(3)$▫.
    Source: Algebraic and topological graph theory (Str. 1812-1819)
    Type of material - conference contribution
    Publish date - 2010
    Language - english
    COBISS.SI-ID - 15553113

    Link(s):

    http://dx.doi.org/10.1016/j.disc.2009.12.009

Shelf entry