Expand all Collapse all | Results 1 - 25 of 59 |
1. CMB Online first
Cover products and Betti polynomials 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 Castelnuovo--Mumford
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:Castelnuovo--Mumford regularity, chordal bipartite graph, edge ideal, graded Betti number, induced matching number, monomial ideal Categories:13D02, 05E45 |
2. CMB Online first
On domination of zero-divisor graphs of matrix rings We study domination in zero-divisor graphs of matrix rings over a
commutative ring with $1$.
Keywords:vector space, linear transformation, zero-divisor graph, domination, local ring Category:05C69 |
3. CMB Online first
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, k-1\}$, 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 worst-case
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 $c|G|$, where
$c\lt 1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar
graphs but has polynomial-time solution for forests.
Keywords:spread of influence in graphs, irreversible dynamic monopolies, target set selection Categories:05C69, 05C85 |
4. CMB Online first
Coloring Four-uniform Hypergraphs on Nine Vertices Every 4-uniform hypergraph on 9 vertices
with at most 25 edges has property B.
This gives the answer $m_9(4)=26$ to a question
raised in 1968 by ErdÅs.
Keywords:property B, coloring hypergraphs Category:05C15 |
5. CMB Online first
Path Decompositions of Kneser and Generalized Kneser Graphs Necessary and sufficient conditions are given for the existence
of a graph decomposition of the Kneser Graph $KG_{n,2}$ and of
the Generalized Kneser Graph $GKG_{n,3,1}$ into paths of length
three.
Keywords:Kneser graph, generalized Kneser graph, path decomposition, graph decomposition Categories:05C51, 05C70 |
6. CMB 2014 (vol 58 pp. 105)
On Graphs Associated with Character Degrees and Conjugacy Class Sizes of Direct Products of Finite Groups |
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 |
7. CMB 2014 (vol 57 pp. 658)
Admissibility of Local Systems for some Classes of Line Arrangements Let $\mathcal{A}$ be a line arrangement in the complex
projective plane $\mathbb{P}^2$ and let $M$ be its complement. A rank one
local system $\mathcal{L}$ on $M$ is admissible if roughly speaking
the cohomology groups
$H^m(M,\mathcal{L})$ can be computed directly from the cohomology
algebra $H^{*}(M,\mathbb{C})$. In this work, we give a sufficient
condition for the admissibility of all rank one local systems on
$M$. As a result, we obtain some properties of the characteristic
variety $\mathcal{V}_1(M)$ and the Resonance variety $\mathcal{R}_1(M)$.
Keywords:admissible local system, line arrangement, characteristic variety, multinet, resonance variety Categories:14F99, 32S22, 52C35, 05A18, 05C40, 14H50 |
8. CMB 2014 (vol 57 pp. 573)
Some Results on the Domination Number of a Zero-divisor Graph In this paper, we investigate the domination, total domination and
semi-total domination numbers of a zero-divisor 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:zero-divisor graph, domination number Categories:05C75, 13H10 |
9. CMB 2014 (vol 57 pp. 520)
Maximizing the Index of Trees with Given Domination Number The index of a graph $G$ is the maximum
eigenvalue of its adjacency matrix $A(G)$. In this paper we
characterize the extremal tree with given
domination number that attains the maximum index.
Keywords:trees, spectral radius, index, domination number Category:05C50 |
10. CMB 2013 (vol 57 pp. 72)
Un Anneau Commutatif associÃ© Ã un design symÃ©trique Dans les articles \cite{1}, \cite{2} et \cite{3}; l'auteur dÃ©veloppe une reprÃ©sentation
d'un plan projectif fini par un
anneau commutatif unitaire dont les propriÃ©tÃ©s algÃ©briques dÃ©pendent
de la structure gÃ©omÃ©trique du plan. Dans l'article \cite{4}; il Ã©tend cette reprÃ©sentation aux designs symÃ©triques. Cependant l'auteur de l'article \cite{7} fait remarquer que la multiplication dÃ©finie dans ce cas ne peut Ãªtre associative que si le design est un plan projectif.
Dans ce papier on mÃ¨nera
une Ã©tude de cette reprÃ©sentation dans le cas des designs
symÃ©triques. On y montrera comment on peut faire associer un
anneau commutatif unitaire Ã
tout design symÃ©trique , on y prÃ©cisera certaines de ses propriÃ©tÃ©s, en
particulier, celles qui relÃ¨vent de son invariance. On caractÃ©risera aussi les gÃ©omÃ©tries projectives finies de dimension supÃ©rieure moyennant cette reprÃ©sentation.
Keywords:projective planes, symmetric designs, commutative rings Categories:05B05, 16S99 |
11. CMB 2013 (vol 57 pp. 375)
A Problem on Edge-magic Labelings of Cycles Kotzig and Rosa defined in 1970 the concept of edge-magic labelings as
follows: let $G$ be a simple $(p,q)$-graph (that is, a graph of order $p$
and size $q$ without loops or multiple edges). A bijective function $f:V(G)\cup
E(G)\rightarrow \{1,2,\ldots,p+q\}$ is an edge-magic labeling of $G$ if
$f(u)+f(uv)+f(v)=k$, for all $uv\in E(G)$. A graph that admits an edge-magic
labeling is called an edge-magic graph, and $k$ is called the magic sum
of the labeling. An old conjecture of Godbold and Slater sets that all
possible theoretical magic sums are attained for each cycle of order $n\ge
7$. Motivated by this conjecture, we prove that for all $n_0\in \mathbb{N}$,
there exists $n\in \mathbb{N}$, such that the cycle $C_n$ admits at least
$n_0$ edge-magic labelings with at least $n_0$ mutually distinct magic
sums. We do this by providing a lower bound for the number of magic sums
of the cycle $C_n$, depending on the sum of the exponents of the odd primes
appearing in the prime factorization of $n$.
Keywords:edge-magic, valence, $\otimes_h$-product Category:05C78 |
12. CMB 2013 (vol 57 pp. 225)
Small Flag Complexes with Torsion We classify flag complexes on at most $12$ vertices with torsion in
the first homology group. The result is moderately computer-aided.
As a consequence we confirm a folklore conjecture that the smallest
poset whose order complex is homotopy equivalent to the real
projective plane (and also the smallest poset with torsion in the
first homology group) has exactly $13$ elements.
Keywords:clique complex, order complex, homology, torsion, minimal model Categories:55U10, 06A11, 55P40, 55-04, 05-04 |
13. CMB 2013 (vol 57 pp. 631)
Indicators, Chains, Antichains, Ramsey Property We introduce two Ramsey classes of finite relational structures. The first
class contains finite structures of the form $(A,(I_{i})_{i=1}^{n},\leq
,(\preceq _{i})_{i=1}^{n})$ where $\leq $ is a total ordering on $A$ and $%
\preceq _{i}$ is a linear ordering on the set $\{a\in A:I_{i}(a)\}$. The
second class contains structures of the form $(A,\leq
,(I_{i})_{i=1}^{n},\preceq )$ where $(A,\leq )$ is a weak ordering and $%
\preceq $ is a linear ordering on $A$ such that $A$ is partitioned by $%
\{a\in A:I_{i}(a)\}$ into maximal chains in the partial ordering $\leq $ and
each $\{a\in A:I_{i}(a)\}$ is an interval with respect to $\preceq $.
Keywords:Ramsey property, linear orderings Categories:05C55, 03C15, 54H20 |
14. CMB 2013 (vol 57 pp. 141)
Size, Order, and Connected Domination We give a sharp upper bound on the size of a
triangle-free graph of a given order and connected domination. Our
bound, apart from
strengthening an old classical theorem of Mantel and of
TurÃ¡n , improves on a theorem of Sanchis.
Further, as corollaries, we settle a long standing
conjecture of Graffiti on the leaf number and local independence for
triangle-free graphs and answer a question of Griggs, Kleitman and
Shastri on a lower bound of the leaf number in
triangle-free graphs.
Keywords:size, connected domination, local independence number, leaf number Category:05C69 |
15. CMB 2013 (vol 57 pp. 188)
A Characterization of Bipartite Zero-divisor Graphs In this paper we obtain a characterization for all bipartite
zero-divisor graphs of commutative rings $R$ with $1$, such that
$R$ is finite or $|Nil(R)|\neq2$.
Keywords:zero-divisor graph, bipartite graph Categories:13AXX, 05C25 |
16. CMB 2013 (vol 56 pp. 449)
The $f$-Chromatic Index of a Graph Whose $f$-Core has Maximum Degree $2$ Let $G$ be a graph. The minimum number of colors needed to color the edges of
$G$ is called the chromatic index of $G$ and is denoted by $\chi'(G)$.
It is well-known that $\Delta(G) \leq \chi'(G) \leq \Delta(G)+1$, for any
graph $G$, where $\Delta(G)$ denotes the maximum degree of $G$. A graph $G$ is said to be
Class $1$ if $\chi'(G) = \Delta(G)$ and Class $2$ if
$\chi'(G) = \Delta(G) + 1$. Also, $G_\Delta$ is the induced subgraph on all vertices of degree $\Delta(G)$.
Let $f:V(G)\rightarrow \mathbb{N}$ be a function.
An $f$-coloring of a graph $G$ is a coloring of the edges
of $E(G)$ such that each color appears at each vertex $v\in V(G)$ at
most $f (v)$ times. The minimum number of colors needed
to $f$-color $G$ is called the $f$-chromatic index of $G$ and
is denoted by $\chi'_{f}(G)$. It was shown that for every graph $G$, $\Delta_{f}(G)\le \chi'_{f}(G)\le \Delta_{f}(G)+1$, where $\Delta_{f}(G)=\max_{v\in V(G)} \big\lceil \frac{d_G(v)}{f(v)}\big\rceil$. A graph $G$ is said to be $f$-Class $1$ if $\chi'_{f}(G)=\Delta_{f}(G)$, and $f$-Class $2$, otherwise. Also, $G_{\Delta_f}$ is the induced subgraph of $G$ on $\{v\in V(G):\,\frac{d_G(v)}{f(v)}=\Delta_{f}(G)\}$.
Hilton and Zhao showed that if $G_{\Delta}$ has maximum degree two and $G$ is Class $2$, then $G$ is critical, $G_{\Delta}$ is a disjoint union of cycles and $\delta(G)=\Delta(G)-1$, where $\delta(G)$ denotes the minimum degree of $G$, respectively. In this paper, we generalize this theorem to $f$-coloring of graphs. Also, we determine the $f$-chromatic index of a connected graph $G$ with $|G_{\Delta_f}|\le 4$.
Keywords:$f$-coloring, $f$-Core, $f$-Class $1$ Categories:05C15, 05C38 |
17. CMB Online first
An Explicit Formula for the Generalized Cyclic Shuffle Map We provide an explicit formula for the generalized cyclic shuffle map for cylindrical modules.
Using this formula we give a combinatorial proof of the generalized
cyclic Eilenberg-Zilber theorem.
Keywords:generalized Cyclic shuffle map, Cylindrical module, Eilenberg-Zilber theorem, Cyclic homology Categories:19D55, 05E45 |
18. CMB 2013 (vol 57 pp. 210)
An Explicit Formula for the Generalized Cyclic Shuffle Map We provide an explicit formula for the generalized cyclic shuffle map for cylindrical modules.
Using this formula we give a combinatorial proof of the generalized
cyclic Eilenberg-Zilber theorem.
Keywords:generalized Cyclic shuffle map, Cylindrical module, Eilenberg-Zilber theorem, Cyclic homology Categories:19D55, 05E45 |
19. CMB 2012 (vol 56 pp. 709)
Universal Minimal Flows of Groups of Automorphisms of Uncountable Structures It is a well-known fact, that the greatest ambit for
a topological group $G$ is the Samuel compactification of $G$ with
respect to the right uniformity on $G.$ We apply the original
description by Samuel from 1948 to give a simple computation of the
universal minimal flow for groups of automorphisms of uncountable
structures using FraÃ¯ssÃ© theory and Ramsey theory. This work
generalizes some of the known results about countable structures.
Keywords:universal minimal flows, ultrafilter flows, Ramsey theory Categories:37B05, 03E02, 05D10, 22F50, 54H20 |
20. CMB 2011 (vol 55 pp. 418)
Maximal Sets of Pairwise Orthogonal Vectors in Finite Fields Given a positive integer $n$, a finite field $\mathbb{F}_q$ of $q$ elements
($q$ odd), and a non-degenerate symmetric bilinear form $B$ on
$\mathbb{F}_q^n$, we determine the largest possible cardinality of pairwise
$B$-orthogonal subsets $\mathcal{E} \subseteq \mathbb{F}_q^n$, that is, for
any two vectors $\mathbf{x}, \mathbf{y} \in \mathcal{E}$, one has $B
(\mathbf{x}, \mathbf{y}) = 0$.
Keywords:orthogonal sets, zero-distance sets Category:05B25 |
21. CMB 2011 (vol 56 pp. 265)
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, close-end 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 |
22. CMB 2011 (vol 56 pp. 407)
On Domination in Zero-Divisor Graphs We first determine the domination number for the zero-divisor
graph of the product of two commutative rings with $1$. We then
calculate the domination number for the zero-divisor graph of any
commutative artinian ring. Finally, we extend some of the results
to non-commutative rings in which an element is a left
zero-divisor if and only if it is a right zero-divisor.
Keywords:zero-divisor graph, domination Categories:13AXX, 05C69 |
23. CMB 2011 (vol 55 pp. 462)
Hook-content Formulae for Symplectic and Orthogonal Tableaux By considering the specialisation
$s_{\lambda}(1,q,q^2,\dots,q^{n-1})$ of
the Schur function, Stanley was able to describe a formula for the
number of semistandard Young tableaux of shape $\lambda$ in terms of
the contents and hook lengths of the boxes in the Young diagram.
Using specialisations of symplectic and orthogonal Schur functions,
we derive corresponding formulae,
first given by El Samra and King, for the number of semistandard
symplectic and orthogonal $\lambda$-tableaux.
Keywords:symplectic tableaux, orthogonal tableaux, Schur function Categories:05E05, 05E10 |
24. CMB 2011 (vol 55 pp. 410)
A Ramsey Theorem with an Application to Sequences in Banach Spaces The notion of a maximally conditional sequence is introduced for sequences in a Banach space. It is then proved using
Ramsey theory that every basic sequence in a Banach space has a subsequence which is either an unconditional
basic sequence or a maximally conditional sequence. An apparently novel, purely combinatorial lemma in the spirit of
Galvin's theorem is used in the proof. An alternative proof
of the dichotomy result for sequences in Banach spaces is
also sketched,
using the Galvin-Prikry theorem.
Keywords:Banach spaces, Ramsey theory Categories:46B15, 05D10 |
25. CMB 2011 (vol 54 pp. 255)
On an Identity due to Bump and Diaconis, and Tracy and Widom
A classical question for a Toeplitz matrix with given symbol is how to
compute asymptotics for the determinants of its reductions to finite
rank. One can also consider how those asymptotics are affected when
shifting an initial set of rows and columns (or, equivalently,
asymptotics of their minors). Bump and Diaconis
obtained a formula for such shifts involving Laguerre polynomials and
sums over symmetric groups. They also showed how the Heine identity
extends for such minors, which makes this question relevant to Random
Matrix Theory. Independently, Tracy and Widom
used the Wiener-Hopf factorization to
express those shifts in terms of products of infinite matrices. We
show directly why those two expressions are equal and uncover some
structure in both formulas that was unknown to their authors. We
introduce a mysterious differential operator on symmetric functions
that is very similar to vertex operators. We show that the
Bump-Diaconis-Tracy-Widom identity is a differentiated version of the
classical Jacobi-Trudi identity.
Keywords:Toeplitz matrices, Jacobi-Trudi identity, SzegÅ limit theorem, Heine identity, Wiener-Hopf factorization Categories:47B35, 05E05, 20G05 |