location:  Publications → journals
Search results

Search: MSC category 05 ( Combinatorics )

 Expand all        Collapse all Results 1 - 25 of 81

1. 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 tableauCategories:05E10, 17B37

2. CMB Online first

Cames van Batenburg, Wouter; Kang, Ross J.
 Squared chromatic number without claws or large cliques Let $G$ be a claw-free graph on $n$ vertices with clique number $\omega$, and consider the chromatic number $\chi(G^2)$ of the square $G^2$ of $G$. Writing $\chi'_s(d)$ for the supremum of $\chi(L^2)$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $\chi(G^2)\le \chi'_s(\omega)$ for $\omega \in \{3,4\}$. For $\omega=3$, this implies the sharp bound $\chi(G^2) \leq 10$. For $\omega=4$, this implies $\chi(G^2)\leq 22$, which is within $2$ of the conjectured best bound. This work is motivated by a strengthened form of a conjecture of ErdÅs and NeÅ¡etÅil. Keywords:graph colouring, ErdÅs-NeÅ¡etÅil conjecture, claw-free graphCategories:05C15, 05C35, 05C70

3. 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 2-section of the hypergraph in question, determining a minimum strong vertex cut is NP-hard for general hypergraphs. Moreover, the problem of finding minimum strong vertex cuts remains NP-hard 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 NP-hard while the other can be solved in polynomial time. Keywords:hypergraph, connectivity, computational complexity, transversalCategories:05C65, 05C40, 68Q17

4. 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 symmetryCategories:46LXX, 05CXX, 20B25

5. 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 embeddingCategory:05C10

6. CMB 2017 (vol 60 pp. 319)

 The Weakly Nilpotent Graph of a Commutative Ring Let $R$ be a commutative ring with non-zero 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 non-zero 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, zero-divisor graph, diameter, girthCategories:05C15, 16N40, 16P20

7. CMB 2016 (vol 60 pp. 26)

Azimi, Ali; Farrokhi Derakhshandeh Ghouchan, Mohammad
 Self $2$-distance Graphs All finite simple self $2$-distance graphs with no square, diamond, or triangles with a common vertex as subgraph are determined. Utilizing these results, it is shown that there is no cubic self $2$-distance graph. Keywords:distance graph, regular graph, forbidden subgraphCategories:05C12, 05C60, 05C76

8. 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 $(r-1)n^2 + 1$. Keywords:determinantal hypersurface, matrix invariant, $q$-binomial coefficientCategories:14M12, 15A22, 05A10

9. CMB 2016 (vol 60 pp. 12)

Akbari, Saieed; Miraftab, Babak; Nikandish, Reza
 Co-maximal Graphs of Subgroups of Groups Let $H$ be a group. The co-maximal graph of subgroups of $H$, denoted by $\Gamma(H)$, is a graph whose vertices are non-trivial 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 co-maximal 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 co-maximal graph of a general linear group over an algebraically closed field is zero or infinite. Keywords:co-maximal graphs of subgroups of groups, diameter, nilpotent group, solvable groupCategories:05C25, 05E15, 20D10, 20D15

10. CMB 2016 (vol 60 pp. 43)

Bouchemakh, Isma; Fatma, Kaci
 On the Dual KÃ¶nig Property of the Order-interval Hypergraph of Two Classes of N-free Posets Let $P$ be a finite N-free poset. We consider the hypergraph $\mathcal{H}(P)$ whose vertices are the elements of $P$ and whose edges are the maximal intervals of $P$. We study the dual KÃ¶nig property of $\mathcal{H}(P)$ in two subclasses of N-free class. Keywords:poset, interval, N-free, hypergraph, KÃ¶nig property, dual KÃ¶nig propertyCategory:05C65

11. 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 graphCategories:05C12, 05C35

12. 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 Church-Farb. Keywords:chromatic functor, stable partition, representation stabilityCategories:05C15, 20C30

13. 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_{n-1}$ and the~edges $v_i v_{i+j}$, where $0 \le i \le n-1$, $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), 47--54] 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+p-1$ 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, distanceCategories:05C35, 05C12

14. CMB 2016 (vol 59 pp. 794)

Hashemi, Ebrahim; Amirjan, R.
 Zero-divisor Graphs of Ore Extensions over Reversible Rings Let $R$ be an associative ring with identity. First we prove some results about zero-divisor graphs of reversible rings. Then we study the zero-divisors 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 zero-divisor graphs of $\Gamma(R)$, $\Gamma(R[x;\alpha,\delta])$ and $\Gamma(R[[x;\alpha]])$, when $R$ is reversible and $(\alpha,\delta)$-compatible. Keywords:zero-divisor graphs, reversible rings, McCoy rings, polynomial rings, power series ringsCategories:13B25, 05C12, 16S36

15. CMB 2016 (vol 59 pp. 652)

 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 $x-y$ 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)$ self-injective 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, self-injective ringCategories:05C25, 16U60, 05C12

16. 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 graphCategory:05C10

17. CMB 2016 (vol 59 pp. 641)

 Some Results on the Annihilating-ideal Graphs The annihilating-ideal graph of a commutative ring $R$, denoted by $\mathbb{AG}(R)$, is a graph whose vertex set consists of all non-zero 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 annihilating-ideal graph of a ring. For example, it is shown that every bipartite annihilating-ideal 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:annihilating-ideal graph, independence number, edge chromatic number, bipartite, cycleCategories:05C15, 05C69, 13E05, 13E10

18. 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 dimensionCategories:13M99, 05E40

19. CMB 2016 (vol 59 pp. 440)

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, cycleCategory:05C15

20. 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 (k-1)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 (k-1+\epsilon) w$ when $w$ is large (depending on $\epsilon$). Several possible generalizations of the problem are also discussed. Keywords:block design, hypergraphCategory:05C70

21. 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 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, cycleCategories:05C15, 05C55, 05C65

22. CMB 2015 (vol 59 pp. 170)

Martínez-Pedroza, 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 groupsCategories:20F67, 05C10, 20J05, 57M60

23. CMB 2015 (vol 59 pp. 36)

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 numbersCategories:20N05, 05B07

24. 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 decompositionCategories:05C51, 05C70

25. 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 idealCategories:13D02, 05E45
 Page 1 2 3 4 Next
 top of page | contact us | privacy | site map |