CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  Publicationsjournals
Publications        
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 1 - 25 of 61

1. CMB Online first

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 m-1$, 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}\rceil-2$ 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

2. CMB Online first

Donovan, Diane M.; Griggs, Terry S.; McCourt, Thomas A.; Opršal, Jakub; Stanovský, David
Distributive and anti-distributive 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 anti-mitre Steiner triple systems respectively.

Keywords:Mendelsohn triple system, quasigroup, distributive, Moufang loop, Loeschian numbers
Categories:20N05, 05B07

3. CMB 2015 (vol 58 pp. 610)

Rodger, C. A.; Whitt, Thomas Richard
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

4. CMB Online first

Zhang, Haihui
A note on 3-choosability 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) 68-71) conjectured that every planar graph without cycles of length 4, 5, 6, is 3-choosable. In this paper, we prove that every planar graph without 5-, 6- and 10-cycles, and without two triangles at distance less than 3 is 3-choosable.

Keywords:choosability, planar graph, cycle
Category:05C15

5. CMB 2015 (vol 58 pp. 320)

Llamas, Aurora; Martínez-Bernal, 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 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

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

7. CMB 2015 (vol 58 pp. 271)

Jafari, Sayyed Heidar; Jafari Rad, Nader
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

8. CMB 2015 (vol 58 pp. 317)

Lewkowicz, Marek Kazimierz
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

9. CMB 2014 (vol 58 pp. 105)

Hossein-Zadeh, 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

10. CMB 2014 (vol 57 pp. 658)

Thang, Nguyen Tat
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

11. CMB 2014 (vol 57 pp. 573)

Kiani, Sima; Maimani, Hamid Reza; Nikandish, Reza
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

12. CMB 2014 (vol 57 pp. 520)

Guo, Guangquan; Wang, Guoping
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

13. CMB 2013 (vol 57 pp. 72)

Grari, A.
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

14. CMB 2013 (vol 57 pp. 375)

López, S. C.; Muntaner-Batle, ; Rius-Font,
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

15. CMB 2013 (vol 57 pp. 225)

Adamaszek, Michał
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

16. CMB 2013 (vol 57 pp. 631)

Sokić, Miodrag
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

17. CMB 2013 (vol 57 pp. 141)

Mukwembi, Simon
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

18. CMB 2013 (vol 57 pp. 188)

Rad, Nader Jafari; Jafari, Sayyed Heidar
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

19. CMB 2013 (vol 56 pp. 449)

Akbari, S.; Chavooshi, M.; Ghanbari, M.; Zare, S.
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

20. CMB 2013 (vol 57 pp. 210)

Zhang, Jiao; Wang, Qing-Wen
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

21. CMB 2012 (vol 56 pp. 709)

Bartošová, Dana
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

22. CMB 2011 (vol 55 pp. 418)

Vinh, Le Anh
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

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

24. CMB 2011 (vol 56 pp. 407)

Rad, Nader Jafari; Jafari, Sayyed Heidar; Mojdeh, Doost Ali
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

25. CMB 2011 (vol 55 pp. 462)

Campbell, Peter S.; Stokke, Anna
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
Page
   1 2 3    

© Canadian Mathematical Society, 2015 : https://cms.math.ca/