location:  Publications → journals
Search results

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

 Expand all        Collapse all Results 1 - 25 of 34

1. CMB Online first

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

2. CMB Online first

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

3. CMB Online first

 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

4. CMB Online first

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

5. CMB Online first

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

6. CMB Online first

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 graphCategories:13A15, 16N40

7. CMB Online first

 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

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

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

10. 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, spinorsCategories:53A10, 53C42

11. 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, representationCategories:46L05, 37A55

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

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

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

15. 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 selectionCategories:05C69, 05C85

16. CMB 2015 (vol 58 pp. 271)

 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 ringCategory:05C69

17. 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 hypergraphsCategory:05C15

18. CMB 2014 (vol 58 pp. 105)

 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 operationCategories:20E45, 05C25, 05C76

19. CMB 2014 (vol 58 pp. 150)

Ostrovskii, Mikhail I.
 Connections Between Metric Characterizations of Superreflexivity and the Radon-NikodÃ½ Property for Dual Banach Spaces Johnson and Schechtman (2009) characterized superreflexivity in terms of finite diamond graphs. The present author characterized the Radon-NikodÃ½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, Radon-NikodÃ½m property, superreflexivityCategories:46B85, 46B07, 46B22

20. 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 numberCategories:05C75, 13H10

21. 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 graphCategories:13AXX, 05C25

22. CMB 2012 (vol 57 pp. 61)

Geschke, Stefan
 2-dimensional 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 3-cliques in terms of clopen, $P_4$-free graphs on Polish spaces. Keywords:convex cover, convexity number, continuous coloring, perfect graph, cographCategories:52A10, 03E17, 03E75

23. 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, clique-cover number, chromatic numberCategories:03E05, 03E35, 03E55

24. 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 graphsCategory:05C10

25. 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, dominationCategories:13AXX, 05C69
 Page 1 2 Next
 top of page | contact us | privacy | site map |