Unique maximum independent sets in graphs on monomials of a fixed degree

被引：0

作者：

Machacek, John ^{[1
]}

机构：

[1] Hampden Sydney Coll, Dept Math & Comp Sci, Hampden Sydney, VA 23943 USA

来源：

PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM | 2021年 / 195卷

关键词：

Independent sets; domination; integer sequences; DOMINATION; POINTS;

D O I：

10.1016/j.procs.2021.11.036

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider graphs on monomials in n variables of a fixed degree d where two monomials are adjacent if and only if their least common multiple has degree d + 1. We find that when n = 3 and d is divisible by 3 as well as when n = 4 and d is even that these graphs have a unique maximum independent set. Domination in these graphs is also considered, and we conjecture that there is equality of the domination number and independent domination number in all cases. (C) 2021 The Authors. Published by Elsevier B.V.

引用

页码：289 / 297

页数：9

共 15 条

[1] DOMINATION AND INDEPENDENT DOMINATION NUMBERS OF A GRAPH [J].

ALLAN, RB ;

LASKAR, R .

DISCRETE MATHEMATICS, 1978, 23 (02) :73-76

[2]

Babcock B, 2013, AUSTRALAS J COMB, V56, P77

[3] GRAPH-THEORETIC PARAMETERS CONCERNING DOMINATION, INDEPENDENCE, AND IRREDUNDANCE [J].

BOLLOBAS, B ;

COCKAYNE, EJ .

JOURNAL OF GRAPH THEORY, 1979, 3 (03) :241-249

[4] Computing the spreading and covering numbers [J].

Carlini, E ;

Hà, HT ;

Van Tuyl, A .

COMMUNICATIONS IN ALGEBRA, 2001, 29 (12) :5687-5699

[5] A COMBINATORIAL PROBLEM INVOLVING MONOMIAL IDEALS [J].

CURTIS, FJ .

JOURNAL OF PURE AND APPLIED ALGEBRA, 1995, 104 (02) :161-167

[6]

DeMaio J., 2013, The College Mathematics Journal, V44, P307

[7] MONOMIAL IDEALS AND POINTS IN PROJECTIVE-SPACE [J].

GERAMITA, AV ;

GREGORY, D ;

ROBERTS, L .

JOURNAL OF PURE AND APPLIED ALGEBRA, 1986, 40 (01) :33-62

[8] GRAPHS WITH UNIQUE MAXIMUM INDEPENDENT SETS [J].

HOPKINS, G ;

STATON, W .

DISCRETE MATHEMATICS, 1985, 57 (03) :245-251

[9] Generating monomials in dimensions three and four [J].

Hulett, H ;

Will, TG .

JOURNAL OF PURE AND APPLIED ALGEBRA, 1999, 138 (02) :139-150

[10]

OEIS Foundation Inc, The On-Line Encyclopedia of Integer Sequences

← 1 2 →