location:  Publications → journals
Search results

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

 Expand all        Collapse all Results 1 - 14 of 14

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

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

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

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

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

6. CMB 2009 (vol 53 pp. 378)

Zhou, Sizhong
 A New Sufficient Condition for a Graph To Be $(g,f,n)$-Critical Let $G$ be a graph of order $p$, let $a$, $b$, and $n$ be nonnegative integers with $1\leq a\lt b$, and let $g$ and $f$ be two integer-valued functions defined on $V(G)$ such that $a\leq g(x)\lt f(x)\leq b$ for all $x\in V(G)$. A $(g,f)$-factor of graph $G$ is a spanning subgraph $F$ of $G$ such that $g(x)\leq d_F(x)\leq f(x)$ for each $x\in V(F)$. Then a graph $G$ is called $(g,f,n)$-critical if after deleting any $n$ vertices of $G$ the remaining graph of $G$ has a $(g,f)$-factor. The binding number $\operatorname{bind}(G)$ of $G$ is the minimum value of ${|N_G(X)|}/{|X|}$ taken over all non-empty subsets $X$ of $V(G)$ such that $N_G(X)\neq V(G)$. In this paper, it is proved that $G$ is a $(g,f,n)$-critical graph if $\operatorname{bind}(G)\gt \frac{(a+b-1)(p-1)}{(a+1)p-(a+b)-bn+2} \quad\text{and}\quad p\geq \frac{(a+b-1)(a+b-2)}{a+1}+\frac{bn}{a}.$ Furthermore, it is shown that this result is best possible in some sense. Keywords:graph, $(g,f)$-factor, $(g,f,n)$-critical graph, binding numberCategory:05C70

7. CMB 2009 (vol 52 pp. 416)

Malik, Shabnam; Qureshi, Ahmad Mahmood; Zamfirescu, Tudor
 Hamiltonian Properties of Generalized Halin Graphs A Halin graph is a graph $H=T\cup C$, where $T$ is a tree with no vertex of degree two, and $C$ is a cycle connecting the end-vertices of $T$ in the cyclic order determined by a plane embedding of $T$. In this paper, we define classes of generalized Halin graphs, called $k$-Halin graphs, and investigate their Hamiltonian properties. Keywords:$k$-Halin graph, Hamiltonian, Hamiltonian connected, traceableCategories:05C45, 05C38

8. CMB 2009 (vol 52 pp. 257)

Ikeda, Toru
 Essential Surfaces in Graph Link Exteriors An irreducible graph manifold $M$ contains an essential torus if it is not a special Seifert manifold. Whether $M$ contains a closed essential surface of negative Euler characteristic or not depends on the difference of Seifert fibrations from the two sides of a torus system which splits $M$ into Seifert manifolds. However, it is not easy to characterize geometrically the class of irreducible graph manifolds which contain such surfaces. This article studies this problem in the case of graph link exteriors. Keywords:Graph link, Graph manifold, Seifert manifold, Essential surfaceCategory:57M25

9. CMB 2008 (vol 51 pp. 535)

Csorba, Péter
 On the Simple $\Z_2$-homotopy Types of Graph Complexes and Their Simple $\Z_2$-universality We prove that the neighborhood complex $\N(G)$, the box complex $\B(G)$, the homomorphism complex $\Hom(K_2,G)$and the Lov\'{a}sz complex $\L(G)$ have the same simple $\Z_2$-homotopy type in the sense of Whitehead. We show that these graph complexes are simple $\Z_2$-universal. Keywords:graph complexes, simple $\Z_2$-homotopy, universalityCategories:57Q10, 05C10, 55P10

10. CMB 2007 (vol 50 pp. 504)

Dukes, Peter; Ling, Alan C. H.
 Asymptotic Existence of Resolvable Graph Designs Let $v \ge k \ge 1$ and $\lam \ge 0$ be integers. A \emph{block design} $\BD(v,k,\lambda)$ is a collection $\cA$ of $k$-subsets of a $v$-set $X$ in which every unordered pair of elements from $X$ is contained in exactly $\lambda$ elements of $\cA$. More generally, for a fixed simple graph $G$, a \emph{graph design} $\GD(v,G,\lambda)$ is a collection $\cA$ of graphs isomorphic to $G$ with vertices in $X$ such that every unordered pair of elements from $X$ is an edge of exactly $\lambda$ elements of $\cA$. A famous result of Wilson says that for a fixed $G$ and $\lambda$, there exists a $\GD(v,G,\lambda)$ for all sufficiently large $v$ satisfying certain necessary conditions. A block (graph) design as above is \emph{resolvable} if $\cA$ can be partitioned into partitions of (graphs whose vertex sets partition) $X$. Lu has shown asymptotic existence in $v$ of resolvable $\BD(v,k,\lambda)$, yet for over twenty years the analogous problem for resolvable $\GD(v,G,\lambda)$ has remained open. In this paper, we settle asymptotic existence of resolvable graph designs. Keywords:graph decomposition, resolvable designsCategories:05B05, 05C70, 05B10

11. CMB 2007 (vol 50 pp. 460)

Spielberg, Jack
 Weak Semiprojectivity for Purely Infinite $C^*$-Algebras We prove that a separable, nuclear, purely infinite, simple $C^*$-algebra satisfying the universal coefficient theorem is weakly semiprojective if and only if its $K$-groups are direct sums of cyclic groups. Keywords:Kirchberg algebra, weak semiprojectivity, graph $C^*$-algebraCategories:46L05, 46L80, 22A22

12. CMB 2004 (vol 47 pp. 530)

Iranmanesh, A.; Khosravi, B.
 A Characterization of $PSU_{11}(q)$ Order components of a finite simple group were introduced in [4]. It was proved that some non-abelian simple groups are uniquely determined by their order components. As the main result of this paper, we show that groups $PSU_{11}(q)$ are also uniquely determined by their order components. As corollaries of this result, the validity of a conjecture of J. G. Thompson and a conjecture of W. Shi and J. Bi both on $PSU_{11}(q)$ are obtained. Keywords:Prime graph, order component, finite group,simple groupCategories:20D08, 20D05, 20D60

13. CMB 2003 (vol 46 pp. 122)

Moon, Myoungho
 On Certain Finitely Generated Subgroups of Groups Which Split Define a group $G$ to be in the class $\mathcal{S}$ if for any finitely generated subgroup $K$ of $G$ having the property that there is a positive integer $n$ such that $g^n \in K$ for all $g\in G$, $K$ has finite index in $G$. We show that a free product with amalgamation $A*_C B$ and an $\HNN$ group $A *_C$ belong to $\mathcal{S}$, if $C$ is in $\mathcal{S}$ and every subgroup of $C$ is finitely generated. Keywords:free product with amalgamation, $\HNN$ group, graph of groups, fundamental groupCategories:20E06, 20E08, 57M07

14. CMB 1998 (vol 41 pp. 348)

Tymchatyn, E. D.; Yang, Chang-Cheng
 Characterizing continua by disconnection properties We study Hausdorff continua in which every set of certain cardinality contains a subset which disconnects the space. We show that such continua are rim-finite. We give characterizations of this class among metric continua. As an application of our methods, we show that continua in which each countably infinite set disconnects are generalized graphs. This extends a result of Nadler for metric continua. Keywords:disconnection properties, rim-finite continua, graphsCategories:54D05, 54F20, 54F50
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9389771819114685, "perplexity": 549.4293075432743}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-10/segments/1393999653836/warc/CC-MAIN-20140305060733-00047-ip-10-183-142-35.ec2.internal.warc.gz"}