Counting independent sets in certain classes of (almost) regular graphs

Alexander Burstein; Sergey Kitaev; Toufik Mansour

Counting independent sets in certain classes of (almost) regular graphs

Alexander Burstein, Sergey Kitaev, Toufik Mansour

Research output: Contribution to journal › Article › peer-review

Abstract

We enumerate the independent sets of several classes of regular and almost regular graphs and compute the corresponding generating functions. We also note the relations between these graphs and other combinatorial objects and, in some cases, construct the corresponding bijections.

Original language	English
Pages (from-to)	17-26
Number of pages	10
Journal	Pure Mathematics and Applications
Volume	19
Issue number	2-3
Publication status	Published - 2008

Keywords

independent sets
regular graphs
transfer matrix method
bijection

Cite this

@article{bc5b0ef671f449d8aac141edb9c1402b,

title = "Counting independent sets in certain classes of (almost) regular graphs",

abstract = "We enumerate the independent sets of several classes of regular and almost regular graphs and compute the corresponding generating functions. We also note the relations between these graphs and other combinatorial objects and, in some cases, construct the corresponding bijections. ",

keywords = "independent sets, regular graphs, transfer matrix method, bijection",

author = "Alexander Burstein and Sergey Kitaev and Toufik Mansour",

year = "2008",

language = "English",

volume = "19",

pages = "17--26",

journal = "Pure Mathematics and Applications",

issn = "1218-4586",

number = "2-3",

}

TY - JOUR

T1 - Counting independent sets in certain classes of (almost) regular graphs

AU - Burstein, Alexander

AU - Kitaev, Sergey

AU - Mansour, Toufik

PY - 2008

Y1 - 2008

N2 - We enumerate the independent sets of several classes of regular and almost regular graphs and compute the corresponding generating functions. We also note the relations between these graphs and other combinatorial objects and, in some cases, construct the corresponding bijections.

AB - We enumerate the independent sets of several classes of regular and almost regular graphs and compute the corresponding generating functions. We also note the relations between these graphs and other combinatorial objects and, in some cases, construct the corresponding bijections.

KW - independent sets

KW - regular graphs

KW - transfer matrix method

KW - bijection

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/burkitman_PUMA.pdf

UR - http://puma.dimai.unifi.it/19_2_3.php

M3 - Article

SN - 1218-4586

VL - 19

SP - 17

EP - 26

JO - Pure Mathematics and Applications

JF - Pure Mathematics and Applications

IS - 2-3

ER -

Counting independent sets in certain classes of (almost) regular graphs

Abstract

Keywords

Other files and links

Fingerprint

Cite this