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

Search: All articles in the CMB digital archive with keyword graph

  Expand all        Collapse all Results 1 - 25 of 42

1. CMB Online first

Chen, Yichao; Gao, Xiaojian; Huang, Yuanqiu
Enumerating unlabelled embeddings for digraph embeddings
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

2. CMB Online first

Tran, Anh T.; Yamaguchi, Yoshikazu
The asymptotics of the higher dimensional Reidemeister torsion for exceptional surgeries along twist knots
We determine the asymptotic behavior of the higher dimensional Reidemeister torsion for the graph manifolds obtained by exceptional surgeries along twist knots. We show that all irreducible $\operatorname{SL}_2(\mathbb{C})$-representations of the graph manifold are induced by irreducible metabelian representations of the twist knot group. We also give the set of the limits of the leading coefficients in the higher dimensional Reidemeister torsion explicitly.

Keywords:Reidemeister torsion, graph manifold, asymptotic behavior, exceptional surgery
Categories:57M27, 57M50

3. 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 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, girth
Categories:05C15, 16N40, 16P20

4. 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 subgraph
Categories:05C12, 05C60, 05C76

5. CMB 2016 (vol 60 pp. 3)

Akbari, Saeeid; Alilou, Abbas; Amjadi, Jafar; Sheikholeslami, Seyed Mahmoud
The Co-annihilating-ideal Graphs of Commutative Rings
Let $R$ be a commutative ring with identity. The co-annihilating-ideal graph of $R$, denoted by $\mathcal{A}_R$, is a graph whose vertex set is the set of all non-zero proper ideals of $R$ and two distinct vertices $I$ and $J$ are adjacent whenever ${\operatorname {Ann}}(I)\cap {\operatorname {Ann}}(J)=\{0\}$. In this paper we initiate the study of the co-annihilating ideal graph of a commutative ring and we investigate its properties.

Keywords:commutative ring, co-annihilating ideal graph
Categories:13A15, 16N40

6. 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 group
Categories:05C25, 05E15, 20D10, 20D15

7. 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 property
Category:05C65

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

9. CMB 2016 (vol 59 pp. 806)

Izumiya, Shyuichi
Geometric Interpretation of Lagrangian Equivalence
As an application of the theory of graph-like Legendrian unfoldings, relations of the hidden structures of caustics and wave front propagations are revealed.

Keywords:wave front propagations, big wave fronts, graph-like Legendrian unfoldings, caustics
Categories:58K05, 57R45, 58K60

10. 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, distance
Categories:05C35, 05C12

11. 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 rings
Categories:13B25, 05C12, 16S36

12. 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 $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 ring
Categories:05C25, 16U60, 05C12

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

14. CMB 2016 (vol 59 pp. 641)

Shaveisi, Farzad
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, cycle
Categories:05C15, 05C69, 13E05, 13E10

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

16. 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, cycle
Category:05C15

17. 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, hypergraph
Category:05C70

18. CMB 2015 (vol 59 pp. 50)

Dorfmeister, Josef F.; Inoguchi, Jun-ichi; Kobayashi, Shimpei
On the Bernstein Problem in the Three-dimensional Heisenberg Group
In this note we present a simple alternative proof for the Bernstein problem in the three-dimensional Heisenberg group $\operatorname{Nil}_3$ by using the loop group technique. We clarify the geometric meaning of the two-parameter ambiguity of entire minimal graphs with prescribed Abresch-Rosenberg differential.

Keywords:Bernstein problem, minimal graphs, Heisenberg group, loop groups, spinors
Categories:53A10, 53C42

19. CMB 2015 (vol 59 pp. 95)

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 Cuntz-Krieger uniqueness theorem for graph algebras by means of branching systems.

Keywords:C*-algebra, graph algebra, Leavitt path algebra, branching system, representation
Categories:46L05, 37A55

20. CMB 2015 (vol 59 pp. 3)

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

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

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

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

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

25. 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
Page
   1 2    

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