1. CMB Online first
2. CMB Online first
 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 

3. CMB Online first
 Gonçalves, Daniel; Li, Hui; Royer, Danilo

Faithful representations of graph algebras via branching systems
We continue to investigate branching systems of directed graphs
and their connections with graph algebras. We give a sufficient
condition under which the representation induced from a branching
system of a directed graph is faithful and construct a large
class of branching systems that satisfy this condition. We finish
the paper by providing a proof of the converse of the CuntzKrieger
uniqueness theorem for graph algebras by means of branching systems.
Keywords:C*algebra, graph algebra, Leavitt path algebra, branching system, representation Categories:46L05, 37A55 

4. CMB Online first
 Alfuraidan, Monther Rashed

The Contraction Principle for Multivalued Mappings on a Modular Metric Space with a Graph
We study the existence of fixed points for contraction multivalued
mappings in modular metric spaces endowed with a graph. The
notion of a modular metric on an arbitrary set and the corresponding
modular spaces, generalizing classical modulars over linear spaces
like Orlicz spaces, were recently introduced. This paper can
be seen as a generalization of Nadler's and Edelstein's fixed
point theorems to modular metric spaces endowed with a graph.
Keywords:fixed point theory, modular metric spaces, multivalued contraction mapping, connected digraph. Categories:47H09, 46B20, 47H10, 47E10 

5. CMB 2015 (vol 58 pp. 610)
6. CMB Online first
 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 

7. 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 

8. 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 

9. CMB 2015 (vol 58 pp. 271)
10. CMB 2015 (vol 58 pp. 317)
11. CMB 2014 (vol 58 pp. 105)
 HosseinZadeh, Samaneh; Iranmanesh, Ali; Hosseinzadeh, Mohammad Ali; Lewis, Mark L.

On Graphs Associated with Character Degrees and Conjugacy Class Sizes of Direct Products of Finite Groups
The prime vertex graph, $\Delta (X)$, and the common divisor graph,
$\Gamma (X)$, are two graphs that have been defined on a set of
positive integers $X$.
Some
properties of these graphs have been studied in the cases where either
$X$ is the set of character degrees of a group or $X$ is the set of
conjugacy class sizes of a group. In this paper, we gather some
results on these graphs arising in the context of direct product of
two groups.
Keywords:prime vertex graph, common divisor graph, character degree, class sizes, graph operation Categories:20E45, 05C25, 05C76 

12. CMB 2014 (vol 58 pp. 150)
 Ostrovskii, Mikhail I.

Connections Between Metric Characterizations of Superreflexivity and the RadonNikodÃ½ Property for Dual Banach Spaces
Johnson and Schechtman (2009)
characterized superreflexivity in terms of finite diamond graphs.
The present author characterized the RadonNikodÃ½m property
(RNP) for dual spaces in terms of the infinite diamond. This
paper
is devoted to further study of relations between metric
characterizations of superreflexivity and the RNP for dual spaces.
The main result is that finite subsets of any set $M$ whose
embeddability characterizes the RNP for dual spaces, characterize
superreflexivity. It is also observed that the converse statement
does not hold, and that $M=\ell_2$ is a counterexample.
Keywords:Banach space, diamond graph, finite representability, metric characterization, RadonNikodÃ½m property, superreflexivity Categories:46B85, 46B07, 46B22 

13. CMB 2014 (vol 57 pp. 573)
 Kiani, Sima; Maimani, Hamid Reza; Nikandish, Reza

Some Results on the Domination Number of a Zerodivisor Graph
In this paper, we investigate the domination, total domination and
semitotal domination numbers of a zerodivisor graph of a
commutative Noetherian ring. Also, some relations between the
domination numbers of $\Gamma(R/I)$ and $\Gamma_I(R)$, and the
domination numbers of $\Gamma(R)$ and $\Gamma(R[x,\alpha,\delta])$,
where $R[x,\alpha,\delta]$ is the Ore extension of $R$, are studied.
Keywords:zerodivisor graph, domination number Categories:05C75, 13H10 

14. CMB 2013 (vol 57 pp. 188)
15. CMB 2012 (vol 57 pp. 61)
 Geschke, Stefan

2dimensional Convexity Numbers and $P_4$free Graphs
For $S\subseteq\mathbb R^n$ a set
$C\subseteq S$ is an $m$clique if the convex hull of no $m$element subset of
$C$ is contained in $S$.
We show that there is essentially just one way to construct
a closed set $S\subseteq\mathbb R^2$ without an uncountable
$3$clique that is not the union of countably many convex sets.
In particular, all such sets have the same convexity number;
that is, they
require the same number of convex subsets to cover them.
The main result follows from an analysis of the convex structure of closed
sets in $\mathbb R^2$ without uncountable 3cliques in terms of
clopen, $P_4$free graphs on Polish spaces.
Keywords:convex cover, convexity number, continuous coloring, perfect graph, cograph Categories:52A10, 03E17, 03E75 

16. CMB 2011 (vol 56 pp. 317)
 Dorais, François G.

A Note on Conjectures of F. Galvin and R. Rado
In 1968, Galvin conjectured that an uncountable poset $P$ is the
union of countably many chains if and only if this is true for every
subposet $Q \subseteq P$ with size $\aleph_1$. In 1981, Rado
formulated a similar conjecture that an uncountable interval graph $G$ is countably
chromatic if and only if this is true for every induced subgraph $H
\subseteq G$ with size $\aleph_1$. TodorÄeviÄ has shown
that Rado's Conjecture is consistent relative to the existence of a
supercompact cardinal, while the consistency of Galvin's Conjecture
remains open. In this paper, we survey and collect a variety of
results related to these two conjectures. We also show that the
extension of Rado's conjecture to the class of all chordal graphs is
relatively consistent with the existence of a supercompact cardinal.
Keywords:Galvin conjecture, Rado conjecture, perfect graph, comparability graph, chordal graph, cliquecover number, chromatic number Categories:03E05, 03E35, 03E55 

17. CMB 2011 (vol 56 pp. 265)
 Chen, Yichao; Mansour, Toufik; Zou, Qian

Embedding Distributions of Generalized Fan Graphs
Total embedding distributions have been known for a few classes of graphs.
Chen, Gross, and Rieper
computed it for necklaces, closeend ladders and cobblestone
paths. Kwak and Shim computed it for bouquets of circles and
dipoles. In this paper, a splitting theorem is generalized
and the embedding distributions of
generalized fan graphs are obtained.
Keywords:total embedding distribution, splitting theorem, generalized fan graphs Category:05C10 

18. CMB 2011 (vol 56 pp. 407)
 Rad, Nader Jafari; Jafari, Sayyed Heidar; Mojdeh, Doost Ali

On Domination in ZeroDivisor Graphs
We first determine the domination number for the zerodivisor
graph of the product of two commutative rings with $1$. We then
calculate the domination number for the zerodivisor graph of any
commutative artinian ring. Finally, we extend some of the results
to noncommutative rings in which an element is a left
zerodivisor if and only if it is a right zerodivisor.
Keywords:zerodivisor graph, domination Categories:13AXX, 05C69 

19. CMB 2009 (vol 53 pp. 378)
 Zhou, Sizhong

A New Sufficient Condition for a Graph To Be $(g,f,n)$Critical
Let $G$ be a graph of order $p$, let $a$,
$b$, and $n$ be nonnegative integers with $1\leq a\lt b$, and let $g$
and $f$ be two integervalued functions defined on $V(G)$ such
that $a\leq g(x)\lt f(x)\leq b$ for all $x\in V(G)$. A $(g,f)$factor
of graph $G$ is a spanning subgraph $F$ of $G$ such
that $g(x)\leq d_F(x)\leq f(x)$ for each $x\in V(F)$. Then a graph
$G$ is called $(g,f,n)$critical if after deleting any $n$
vertices of $G$ the remaining graph of $G$ has a $(g,f)$factor.
The binding number $\operatorname{bind}(G)$ of $G$ is the minimum value of
${N_G(X)}/{X}$ taken over all nonempty subsets $X$ of
$V(G)$ such that $N_G(X)\neq V(G)$. In this paper, it is proved
that $G$ is a $(g,f,n)$critical graph if
\[
\operatorname{bind}(G)\gt \frac{(a+b1)(p1)}{(a+1)p(a+b)bn+2}
\quad\text{and}\quad p\geq
\frac{(a+b1)(a+b2)}{a+1}+\frac{bn}{a}.
\]
Furthermore, it is
shown that this
result is best possible in some sense.
Keywords:graph, $(g,f)$factor, $(g,f,n)$critical graph, binding number Category:05C70 

20. CMB 2009 (vol 52 pp. 416)
 Malik, Shabnam; Qureshi, Ahmad Mahmood; Zamfirescu, Tudor

Hamiltonian Properties of Generalized Halin Graphs
A Halin graph is a graph $H=T\cup C$, where $T$ is a tree with no
vertex of degree two, and $C$ is a cycle connecting the endvertices
of $T$ in the cyclic order determined by a plane embedding of $T$.
In this paper, we define classes of generalized Halin graphs, called
$k$Halin graphs, and investigate their Hamiltonian properties.
Keywords:$k$Halin graph, Hamiltonian, Hamiltonian connected, traceable Categories:05C45, 05C38 

21. CMB 2009 (vol 52 pp. 257)
 Ikeda, Toru

Essential Surfaces in Graph Link Exteriors
An irreducible graph manifold $M$ contains an essential torus if
it is not a special Seifert manifold.
Whether $M$ contains a closed essential surface of
negative Euler characteristic or not
depends on the difference of Seifert fibrations from the two sides
of a torus system which splits $M$ into Seifert manifolds.
However,
it is not easy to characterize geometrically the class of
irreducible graph manifolds which contain such surfaces.
This article studies this problem in the case of graph link exteriors.
Keywords:Graph link, Graph manifold, Seifert manifold, Essential surface Category:57M25 

22. CMB 2008 (vol 51 pp. 535)
23. CMB 2007 (vol 50 pp. 504)
 Dukes, Peter; Ling, Alan C. H.

Asymptotic Existence of Resolvable Graph Designs
Let $v \ge k \ge 1$ and $\lam \ge 0$ be integers. A \emph{block
design} $\BD(v,k,\lambda)$ is a collection $\cA$ of $k$subsets of a
$v$set $X$ in which every unordered pair of elements from $X$ is
contained in exactly $\lambda$ elements of $\cA$. More generally, for a
fixed simple graph $G$, a \emph{graph design} $\GD(v,G,\lambda)$ is a
collection $\cA$ of graphs isomorphic to $G$ with vertices in $X$ such
that every unordered pair of elements from $X$ is an edge of exactly
$\lambda$ elements of $\cA$. A famous result of Wilson says that for a
fixed $G$ and $\lambda$, there exists a $\GD(v,G,\lambda)$ for all
sufficiently large $v$ satisfying certain necessary conditions. A
block (graph) design as above is \emph{resolvable} if $\cA$ can be
partitioned into partitions of (graphs whose vertex sets partition)
$X$. Lu has shown asymptotic existence in $v$ of resolvable
$\BD(v,k,\lambda)$, yet for over twenty years the analogous problem for
resolvable $\GD(v,G,\lambda)$ has remained open. In this paper, we settle
asymptotic existence of resolvable graph designs.
Keywords:graph decomposition, resolvable designs Categories:05B05, 05C70, 05B10 

24. CMB 2007 (vol 50 pp. 460)
 Spielberg, Jack

Weak Semiprojectivity for Purely Infinite $C^*$Algebras
We prove that a separable, nuclear, purely infinite, simple
$C^*$algebra satisfying the universal coefficient theorem
is weakly semiprojective if and only if
its $K$groups are direct sums of cyclic groups.
Keywords:Kirchberg algebra, weak semiprojectivity, graph $C^*$algebra Categories:46L05, 46L80, 22A22 

25. CMB 2004 (vol 47 pp. 530)
 Iranmanesh, A.; Khosravi, B.

A Characterization of $ PSU_{11}(q)$
Order components of a finite simple group were introduced in [4].
It was proved that some nonabelian simple groups are uniquely determined
by their order components. As the main result of this paper, we
show that groups $PSU_{11}(q)$ are also uniquely determined by
their order components. As corollaries of this result, the
validity of a conjecture of J. G. Thompson and a conjecture of W.
Shi and J. Bi both on $PSU_{11}(q)$ are obtained.
Keywords:Prime graph, order component, finite group,simple group Categories:20D08, 20D05, 20D60 
