1. CMB 2018 (vol 61 pp. 252)
 Dewar, Megan; Pike, David; Proos, John

Connectivity in Hypergraphs
In this paper we consider two natural notions of connectivity
for hypergraphs: weak and strong. We prove that the strong
vertex connectivity of a connected hypergraph is bounded by its
weak edge connectivity, thereby extending a theorem of Whitney
from graphs to hypergraphs. We find that while determining a
minimum weak vertex cut can be done in polynomial time and is
equivalent to finding a minimum vertex cut in the 2section of
the hypergraph in question, determining a minimum strong vertex
cut is NPhard for general hypergraphs. Moreover, the problem
of finding minimum strong vertex cuts remains NPhard when restricted
to hypergraphs with maximum edge size at most 3. We also discuss
the relationship between strong vertex connectivity and the
minimum
transversal problem for hypergraphs, showing that there are
classes
of hypergraphs for which one of the problems is NPhard while
the other can be solved in polynomial time.
Keywords:hypergraph, connectivity, computational complexity, transversal Categories:05C65, 05C40, 68Q17 

2. CMB Online first
 Schmidt, Simon; Weber, Moritz

Quantum symmetries of graph $C^*$algebras
The study of graph $C^*$algebras has a long history in operator
algebras. Surprisingly, their quantum symmetries have never been
computed so far. We close this gap by proving that the quantum
automorphism group of a finite, directed graph without multiple
edges acts maximally on the corresponding graph $C^*$algebra.
This shows that the quantum symmetry of a graph coincides with
the quantum symmetry of the graph $C^*$algebra. In our result,
we use the definition of quantum automorphism groups of graphs
as given by Banica in 2005. Note that Bichon gave a different
definition in 2003; our action is inspired from his work. We
review and compare these two definitions and we give a complete
table of quantum automorphism groups (with respect to either
of the two definitions) for undirected graphs on four vertices.
Keywords:finite graph, graph automorphism, automorphism group, quantum automorphism, graph C*algebra, quantum group, quantum symmetry Categories:46LXX, 05CXX, 20B25 

3. CMB Online first
 Criswell, Jackson; Salisbury, Ben; Tingley, Peter W.

PBW bases and marginally large tableaux in types B and C
We explicitly describe the isomorphism between two combinatorial
realizations of Kashiwara's infinity crystal in types B and C.
The first realization is in terms of marginally large tableaux
and the other is in terms of Kostant partitions coming from PBW
bases. We also discuss a stack notation for Kostant partitions
which simplifies that realization.
Keywords:crystal, Kostant partition, Lusztig data, marginally large tableau Categories:05E10, 17B37 

4. CMB 2017 (vol 61 pp. 55)
 Chen, Yichao; Gao, Xiaojian; Huang, Yuanqiu

Enumerating unlabelled embeddings of digraphs
A $2$cell embedding of an Eulerian digraph $D$
into a closed surface is said to be directed if the
boundary of each face is a directed closed walk in $D$. In this
paper, a method is developed with the purpose of enumerating
unlabelled embeddings for an Eulerian digraph. As an application,
we obtain explicit formulas for the number of unlabelled embeddings
of directed bouquets of cycles $B_n$, directed dipoles $OD_{2n}$
and for a class of regular tournaments $T_{2n+1}$.
Keywords:Eulerian digraph, directed embedding, unlabelled embedding Category:05C10 

5. CMB 2017 (vol 60 pp. 319)
 Khojasteh, Sohiela; Nikmehr, Mohammad Javad

The Weakly Nilpotent Graph of a Commutative Ring
Let $R$ be a commutative ring with nonzero identity. In this
paper, we introduced the weakly nilpotent graph of a commutative
ring. The weakly nilpotent graph of $R$ is denoted by $\Gamma_w(R)$
is a graph with the vertex set $R^{*}$ and two vertices $x$ and
$y$ are adjacent if and only if $xy\in N(R)^{*}$, where $R^{*}=R\setminus\{0\}$
and $N(R)^{*}$ is the set of all nonzero nilpotent elements
of $R$. In this article, we determine the diameter of weakly
nilpotent graph of an Artinian ring. We prove that if $\Gamma_w(R)$
is a forest, then $\Gamma_w(R)$ is a union of a star and some
isolated vertices. We study the clique number, the chromatic
number and the independence number of $\Gamma_w(R)$. Among other
results, we show that for an Artinian ring $R$, $\Gamma_w(R)$
is not a disjoint union of cycles or a unicyclic graph. For Artinan
ring, we determine $\operatorname{diam}(\overline{\Gamma_w(R)})$. Finally, we
characterize all commutative rings $R$ for which $\overline{\Gamma_w(R)}$
is a cycle, where $\overline{\Gamma_w(R)}$ is the complement
of the weakly nilpotent graph of $R$.
Keywords:weakly nilpotent graph, zerodivisor graph, diameter, girth Categories:05C15, 16N40, 16P20 

6. CMB 2016 (vol 60 pp. 26)
7. CMB 2016 (vol 60 pp. 613)
 Reichstein, Zinovy; Vistoli, Angelo

On the Dimension of the Locus of Determinantal Hypersurfaces
The characteristic polynomial $P_A(x_0, \dots,
x_r)$
of an $r$tuple $A := (A_1, \dots, A_r)$ of $n \times n$matrices
is
defined as
\[ P_A(x_0, \dots, x_r) := \det(x_0 I + x_1 A_1 + \dots + x_r
A_r) \, . \]
We show that if $r \geqslant 3$
and $A := (A_1, \dots, A_r)$ is an $r$tuple of $n \times n$matrices in general position,
then up to conjugacy, there are only finitely many $r$tuples
$A' := (A_1', \dots, A_r')$ such that $p_A = p_{A'}$. Equivalently,
the locus of determinantal hypersurfaces of degree $n$ in $\mathbf{P}^r$
is irreducible of dimension $(r1)n^2 + 1$.
Keywords:determinantal hypersurface, matrix invariant, $q$binomial coefficient Categories:14M12, 15A22, 05A10 

8. CMB 2016 (vol 60 pp. 12)
 Akbari, Saieed; Miraftab, Babak; Nikandish, Reza

Comaximal Graphs of Subgroups of Groups
Let $H$ be a group. The comaximal graph of subgroups
of $H$, denoted by $\Gamma(H)$, is a
graph whose vertices are nontrivial and proper subgroups of
$H$ and two distinct vertices $L$
and $K$ are adjacent in $\Gamma(H)$ if and only if $H=LK$. In
this paper, we study the connectivity, diameter, clique number
and vertex
chromatic number of $\Gamma(H)$. For instance, we show that
if $\Gamma(H)$ has no isolated vertex, then $\Gamma(H)$
is connected with diameter at most $3$. Also, we characterize
all finite groups whose comaximal graphs are connected.
Among other results, we show that if $H$ is a finitely generated
solvable group and $\Gamma(H)$ is connected and moreover the
degree of a maximal subgroup is finite, then $H$ is finite.
Furthermore, we show that the degree of each vertex in the
comaximal graph of a general linear group over an algebraically
closed field is zero or infinite.
Keywords:comaximal graphs of subgroups of groups, diameter, nilpotent group, solvable group Categories:05C25, 05E15, 20D10, 20D15 

9. CMB 2016 (vol 60 pp. 43)
10. CMB 2016 (vol 60 pp. 197)
 Tang, Zikai; Deng, Hanyuan

Degree Kirchhoff Index of Bicyclic Graphs
Let $G$ be a connected graph with vertex set $V(G)$. The degree
Kirchhoff index of $G$ is defined as $S'(G) =\sum_{\{u,v\}\subseteq
V(G)}d(u)d(v)R(u,v)$, where $d(u)$ is the degree of vertex $u$,
and
$R(u, v)$ denotes the resistance distance between vertices $u$
and
$v$. In this paper, we characterize the graphs having maximum
and
minimum degree Kirchhoff index among all $n$vertex bicyclic
graphs
with exactly two cycles.
Keywords:degree Kirchhoff index, resistance distance, bicyclic graph, extremal graph Categories:05C12, 05C35 

11. CMB 2016 (vol 60 pp. 154)
 Liu, Ye

On Chromatic Functors and Stable Partitions of Graphs
The chromatic functor of a simple graph is a functorization of
the chromatic polynomial. M. Yoshinaga showed
that two finite graphs have isomorphic chromatic functors if
and only if they have the same chromatic polynomial. The key
ingredient in the proof is the use of stable partitions of graphs.
The latter is shown to be closely related to chromatic functors.
In this note, we further investigate some interesting properties
of chromatic functors associated to simple graphs using stable
partitions. Our first result is the determination of the group
of natural automorphisms of the chromatic functor, which is in
general a larger group than the automorphism group of the graph.
The second result is that the composition of the chromatic functor
associated to a finite graph restricted to the category $\mathrm{FI}$
of finite sets and injections with the free functor into the
category of complex vector spaces yields a consistent sequence
of representations of symmetric groups which is representation
stable in the sense of ChurchFarb.
Keywords:chromatic functor, stable partition, representation stability Categories:05C15, 20C30 

12. CMB 2016 (vol 60 pp. 206)
 Vetrik, Tomáš

The Metric Dimension of Circulant Graphs
A subset $W$ of the vertex set of a graph $G$ is called a resolving
set of $G$ if for every pair of distinct vertices $u, v$ of $G$,
there is $w \in W$ such that the~distance of $w$ and $u$ is different
from the distance of $w$ and $v$. The~cardinality of a~smallest
resolving set is called the metric dimension of $G$, denoted
by $dim(G)$. The circulant graph $C_n (1, 2, \dots , t)$ consists
of the vertices $v_0, v_1, \dots , v_{n1}$ and the~edges $v_i
v_{i+j}$, where $0 \le i \le n1$, $1 \le j \le t$ $(2 \le t
\le \lfloor \frac{n}{2} \rfloor)$, the indices are taken modulo
$n$. Grigorious et al. [On the metric dimension of circulant
and Harary graphs, Applied Mathematics and Computation 248 (2014),
4754] proved that $dim(C_n (1,2, \dots , t))
\ge t+1$ for $t \lt \lfloor \frac{n}{2} \rfloor$, $n \ge 3$, and they
presented a~conjecture saying that $dim(C_n (1,2, \dots , t))
= t+p1$ for $n=2tk+t+p$, where $3 \le p \le t+1$. We disprove
both statements. We show that if $t \ge 4$ is even, there exists
an infinite set of values of $n$ such that $dim(C_n (1,2, \dots
, t)) = t$. We also prove that $dim(C_n (1,2, \dots , t)) \le
t + \frac{p}{2}$ for $n=2tk+t+p$, where $t$ and $p$ are even,
$t \ge 4$, $2 \le p \le t$ and $k \ge 1$.
Keywords:metric dimension, resolving set, circulant graph, Cayley graph, distance Categories:05C35, 05C12 

13. CMB 2016 (vol 59 pp. 794)
 Hashemi, Ebrahim; Amirjan, R.

Zerodivisor Graphs of Ore Extensions over Reversible Rings
Let $R$ be an associative ring with identity.
First we prove some results about zerodivisor graphs of reversible
rings. Then we study the zerodivisors of the skew power series
ring $R[[x;\alpha]]$, whenever $R$ is reversible and $\alpha$compatible. Moreover, we compare the diameter and girth of the zerodivisor
graphs of $\Gamma(R)$, $\Gamma(R[x;\alpha,\delta])$ and $\Gamma(R[[x;\alpha]])$,
when
$R$ is reversible and $(\alpha,\delta)$compatible.
Keywords:zerodivisor graphs, reversible rings, McCoy rings, polynomial rings, power series rings Categories:13B25, 05C12, 16S36 

14. CMB 2016 (vol 59 pp. 652)
 Su, Huadong

On the Diameter of Unitary Cayley Graphs of Rings
The unitary Cayley graph of a ring $R$, denoted
$\Gamma(R)$, is the simple graph
defined on all elements of $R$, and where two vertices $x$ and
$y$
are adjacent if and only if $xy$ is a unit in $R$. The largest
distance between all pairs of vertices of a graph $G$ is called
the
diameter of $G$, and is denoted by ${\rm diam}(G)$. It is proved
that for each integer $n\geq1$, there exists a ring $R$ such
that
${\rm diam}(\Gamma(R))=n$. We also show that ${\rm
diam}(\Gamma(R))\in \{1,2,3,\infty\}$ for a ring $R$ with $R/J(R)$
selfinjective and classify all those rings with ${\rm
diam}(\Gamma(R))=1$, 2, 3 and $\infty$, respectively.
Keywords:unitary Cayley graph, diameter, $k$good, unit sum number, selfinjective ring Categories:05C25, 16U60, 05C12 

15. CMB 2016 (vol 59 pp. 705)
 Chen, Yichao; Yin, Xuluo

The Thickness of the Cartesian Product of Two Graphs
The thickness of a graph $G$ is the minimum number
of planar subgraphs whose union is $G.$ A
$t$minimal graph is a graph of thickness $t$ which contains
no proper subgraph of thickness $t.$ In this paper, upper and
lower bounds are obtained for the thickness, $t(G\Box H)$, of
the Cartesian
product of two graphs $G$ and $H$, in terms of the thickness
$t(G)$ and $t(H)$.
Furthermore, the thickness of the Cartesian product of two planar
graphs and of a $t$minimal graph and a planar graph are determined.
By using a new planar decomposition of the complete bipartite
graph $K_{4k,4k},$ the thickness of the Cartesian product of
two complete bipartite graphs $K_{n,n}$ and $K_{n,n}$ is also
given, for $n\neq 4k+1$.
Keywords:planar graph, thickness, Cartesian product, $t$minimal graph, complete bipartite graph Category:05C10 

16. CMB 2016 (vol 59 pp. 641)
 Shaveisi, Farzad

Some Results on the Annihilatingideal Graphs
The annihilatingideal graph
of a commutative ring $R$, denoted by $\mathbb{AG}(R)$, is a
graph whose vertex set consists of all nonzero annihilating
ideals and two distinct
vertices $I$ and $J$ are adjacent if and only if $IJ=(0)$. Here,
we show that if $R$ is a reduced ring and the independence
number of $\mathbb{AG}(R)$ is finite, then the edge chromatic
number of $\mathbb{AG}(R)$ equals its maximum degree
and this number equals $2^{{\rm Min}(R)1}1$; also, it is
proved that the independence number of $\mathbb{AG}(R)$ equals
$2^{{\rm Min}(R)1}$, where ${\rm Min}(R)$ denotes the set
of minimal prime ideals of $R$.
Then we give some criteria for a graph to be isomorphic with
an annihilatingideal graph of a ring.
For example, it is shown that every bipartite annihilatingideal
graph is a complete bipartite graph with at most two horns. Among
other results, it is shown that a finite graph $\mathbb{AG}(R)$
is not Eulerian, and it is Hamiltonian if and only if $R$ contains
no Gorenstain ring as its direct summand.
Keywords:annihilatingideal graph, independence number, edge chromatic number, bipartite, cycle Categories:05C15, 05C69, 13E05, 13E10 

17. CMB 2016 (vol 59 pp. 748)
 Dolžan, David

The Metric Dimension of the Total Graph of a Finite Commutative Ring
We study the total graph of a finite commutative ring. We calculate
its metric dimension in the case when the Jacobson radical of
the ring is nontrivial and we examine the metric dimension of
the total graph of a product of at most two fields, obtaining
either exact values in some cases or bounds in other, depending
on the number of elements in the respective fields.
Keywords:total graph, finite ring, metric dimension Categories:13M99, 05E40 

18. CMB 2016 (vol 59 pp. 440)
 Zhang, Haihui

A Note on 3choosability of Planar Graphs Related to Montanssier's Conjecture
A graph $G=(V,E)$ is $L$colorable if for a given list
assignment $L=\{L(v):v\in V(G)\}$, there exists a proper coloring
$c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V$. If $G$ is
$L$colorable for every list assignment $L$ with $L(v)\geq
k$ for
all $v\in V$, then $G$ is said to be $k$choosable. Montassier
(Inform. Process. Lett. 99 (2006) 6871) conjectured that every
planar
graph without cycles of length 4, 5, 6, is 3choosable. In this
paper,
we prove that every planar graph without 5, 6 and 10cycles,
and
without two triangles at distance less than 3 is 3choosable.
Keywords:choosability, planar graph, cycle Category:05C15 

19. CMB 2016 (vol 59 pp. 287)
 Dukes, Peter; Lamken, E.R.; Ling, Alan C.H.

An Existence Theory for Incomplete Designs
An incomplete pairwise balanced design is equivalent to a pairwise
balanced design with a distinguished block, viewed as a `hole'.
If there are $v$ points, a hole of size $w$, and all (other)
block sizes equal $k$, this is denoted IPBD$((v;w),k)$. In addition
to congruence restrictions on $v$ and $w$, there is also a necessary
inequality: $v \gt (k1)w$. This article establishes two main existence
results for IPBD$((v;w),k)$: one in which $w$ is fixed and $v$
is large, and the other in the case $v \gt (k1+\epsilon) w$ when
$w$ is large (depending on $\epsilon$). Several possible generalizations
of the problem are also discussed.
Keywords:block design, hypergraph Category:05C70 

20. CMB 2015 (vol 59 pp. 190)
 Raeisi, Ghaffar; Zaghian, Ali

Ramsey Number of Wheels Versus Cycles and Trees
Let $G_1, G_2, \dots , G_t$ be arbitrary graphs. The
Ramsey number $R(G_1, G_2, \dots, G_t)$ is the smallest positive
integer $n$ such that if the edges of the complete graph $K_n$
are
partitioned into $t$ disjoint color classes giving $t$ graphs
$H_1,H_2,\dots,H_t$, then at least one $H_i$ has a subgraph
isomorphic to $G_i$. In this paper, we provide the exact value
of
the $R(T_n,W_m)$ for odd $m$, $n\geq m1$, where $T_n$ is
either a caterpillar, a tree with diameter at most four or a
tree
with a vertex adjacent to at least $\lceil
\frac{n}{2}\rceil2$ leaves. Also, we
determine $R(C_n,W_m)$ for even integers $n$ and $m$, $n\geq
m+500$, which improves a result of Shi and confirms a
conjecture of Surahmat et al. In addition, the multicolor Ramsey
number of trees
versus an odd wheel is discussed in this paper.
Keywords:Ramsey number, wheel, tree, cycle Categories:05C15, 05C55, 05C65 

21. CMB 2015 (vol 59 pp. 170)
 MartínezPedroza, Eduardo

A Note on Fine Graphs and Homological Isoperimetric Inequalities
In the framework of homological characterizations of relative
hyperbolicity, Groves and Manning posed the question of whether
a simply connected $2$complex $X$ with a linear homological
isoperimetric inequality, a bound on the length of attaching
maps of $2$cells and finitely many $2$cells adjacent to any
edge must have a fine $1$skeleton. We provide a positive answer
to this question. We revisit a homological characterization
of relative hyperbolicity, and show that a group $G$ is hyperbolic
relative to a collection of subgroups $\mathcal P$ if and only if
$G$ acts cocompactly with finite edge stabilizers on an connected
$2$dimensional cell complex with a linear homological isoperimetric
inequality and $\mathcal P$ is a collection of representatives of
conjugacy classes of vertex stabilizers.
Keywords:isoperimetric functions, Dehn functions, hyperbolic groups Categories:20F67, 05C10, 20J05, 57M60 

22. CMB 2015 (vol 59 pp. 36)
 Donovan, Diane M.; Griggs, Terry S.; McCourt, Thomas A.; Opršal, Jakub; Stanovský, David

Distributive and Antidistributive Mendelsohn Triple Systems
We prove that the existence spectrum of Mendelsohn triple systems
whose associated quasigroups satisfy distributivity corresponds
to the Loeschian numbers, and provide some enumeration results.
We do this by considering a description of the quasigroups in
terms of commutative Moufang loops.
In addition we provide constructions of Mendelsohn quasigroups
that fail distributivity for as many combinations of elements
as possible.
These systems are analogues of Hall triple systems and antimitre
Steiner triple systems respectively.
Keywords:Mendelsohn triple system, quasigroup, distributive, Moufang loop, Loeschian numbers Categories:20N05, 05B07 

23. CMB 2015 (vol 58 pp. 610)
24. CMB 2015 (vol 58 pp. 320)
 Llamas, Aurora; MartínezBernal, José

Cover Product and Betti Polynomial of Graphs
For disjoint graphs $G$ and $H$, with fixed
vertex covers
$C(G)$ and $C(H)$, their cover product is the graph $G
\circledast
H$ with vertex set
$V(G)\cup V(H)$ and edge set $E(G)\cup E(H)\cup\{\{i,j\}:i\in
C(G), j\in
C(H)\}$. We describe the graded Betti numbers of $G\circledast
H$ in terms of those of
$G$ and $H$. As applications we obtain: (i) For any positive
integer $k$ there
exists a connected bipartite graph $G$ such that $\operatorname{reg}
R/I(G)=\mu_S(G)+k$, where,
$I(G)$ denotes the edge ideal of $G$, $\operatorname{reg} R/I(G)$
is the CastelnuovoMumford
regularity of $R/I(G)$ and $\mu_S(G)$ is the induced or strong
matching number of
$G$; (ii) The graded Betti numbers of the complement of a tree
only depends upon
its number of vertices; (iii) The $h$vector of $R/I(G\circledast
H)$ is described in
terms of the $h$vectors of $R/I(G)$ and $R/I(H)$. Furthermore,
in a different
direction, we give a recursive formula for the graded Betti numbers
of chordal
bipartite graphs.
Keywords:CastelnuovoMumford regularity, chordal bipartite graph, edge ideal, graded Betti number, induced matching number, monomial ideal Categories:13D02, 05E45 

25. CMB 2015 (vol 58 pp. 306)
 Khoshkhah, Kaveh; Zaker, Manouchehr

On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
Let $G$ be a graph and $\tau$ be an assignment of nonnegative
integer thresholds to the vertices of $G$. A subset of vertices,
$D$ is said to be a $\tau$dynamic monopoly, if $V(G)$ can be
partitioned into subsets $D_0, D_1, \ldots, D_k$ such that $D_0=D$
and for any $i\in \{0, \ldots, k1\}$, each vertex $v$ in $D_{i+1}$
has at least $\tau(v)$ neighbors in $D_0\cup \ldots \cup D_i$.
Denote the size of smallest $\tau$dynamic monopoly by $dyn_{\tau}(G)$
and the average of thresholds in $\tau$ by $\overline{\tau}$.
We show that the values of $dyn_{\tau}(G)$ over all assignments
$\tau$ with the same average threshold is a continuous set of
integers. For any positive number $t$, denote the maximum $dyn_{\tau}(G)$
taken over all threshold assignments $\tau$ with $\overline{\tau}\leq
t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worstcase
value of a dynamic monopoly when the average threshold is a given
number $t$. We investigate under what conditions on $t$, there
exists an upper bound for $Ldyn_{t}(G)$ of the form $cG$, where
$c\lt 1$. Next, we show that $Ldyn_t(G)$ is coNPhard for planar
graphs but has polynomialtime solution for forests.
Keywords:spread of influence in graphs, irreversible dynamic monopolies, target set selection Categories:05C69, 05C85 
