Line Transversals to Disjoint Balls

We prove that the set of directions of lines intersecting three disjoint balls in ℝ³ in a given order is a strictly convex subset of . We then generalize this result to n disjoint balls in ℝ ^d . As a consequence, we can improve upon several old and new results on line transversals to disjoint balls in arbitrary dimension, such as bounds on the number of connected components and Helly-type theorems.     

The Tabular Mode: Not Just Another Way to Represent a Function

Understanding mathematical functions as systematic processes involving the covariation of related variables is foundational in learning mathematics. In this article, findings are reported from two investigations examining students' thinking processes with functions. The first study focused on seven middle school students' explorations with a dynamic physical model. Students were videotaped during the 20‐ to 45‐minute sessions occurring two or three times per week over a period of 2 months, and students' written work was collected. The second investigation included 19 preservice elementary and middle school teachers enrolled in a course focusing on a combination of mathematical content and pedagogy. Participants' written problem‐solving work and reflective writing were collected, and participants were individually interviewed in 50‐minute videotaped sessions. Results from both investigations indicated that students often relied on a table, or some variation of a table, as a cognitive link advancing the development of their reasoning about underlying function relationships.     

The Zero-Divisor Graph Associated to a Semigroup

The zero-divisor graph of a commutative semigroup with zero is the graph whose vertices are the nonzero zero-divisors of the semigroup, with two distinct vertices adjacent if the product of the corresponding elements is zero. New criteria to identify zero-divisor graphs are derived using both graph-theoretic and algebraic methods. We find the lowest bound on the number of edges necessary to guarantee a graph is a zero-divisor graph. In addition, the removal or addition of vertices to a zero-divisor graph is investigated by using equivalence relations and quotient sets. We also prove necessary and sufficient conditions for determining when regular graphs and complete graphs with more than two triangles attached are zero-divisor graphs. Lastly, we classify several graph structures that satisfy all known necessary conditions but are not zero-divisor graphs.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

Bounds to the Chromatic Polynomial of a Graph

In this paper, we present a simple inductive proof of some recently published bounds to the chromatic polynomial of a graph.     

A Pair in a Crowd of Unit Balls

Let F be a family of mutually nonoverlapping unit balls in the n -dimensional Euclidean space Rⁿ. The distance between the centres of A,B   F is denoted by d(A, B). We prove, among others, that if d(A, B)  <  4 and n ≥  5, then A andB are always visible from each other, that is, a light ray emanating from the surface of A reaches B without being blocked by other unit balls. Furthermore, if d(A, B)  < 2n / 2, then any small “shake’ of F can make A, B visible from each other.     

On the Maximum Matching Graph of a Graph

1IntroductionMatchingtheory,aswellastheassignmentprobleminlinearprogramming,hasawiderangeofapplicationinthetheoryandpracticeofoperationsresearch.Bysomepracticalmotivations,e.g.,forfindingalloptimalsolutions,peoplewanttoknowthestructurepropertiesofallmaximummatchingsofagraphG.InthecasethatGhasperfectmatchings,extensiveworkhasbeendoneontheso-calledperfectmatChinggrape(or1-factorgraph),inwhichtwoperfectmatchingsMIandMZaresaidtobeadjacentifMI~MZ@E(C)whereCisanMI-alternatingcycleofG.Therewer…     

Reconstructing a Graph from its Arc Incidence Graph

Introduced implicitly by Brualdi and Massey (Discret Math 122(1–3):51–58, 1993) in their work on the strong chromatic index of multigraphs, the arc incidence graph AI(G) of a graph G is defined as the square of the line graph of the incidence graph of G. We describe a linear-time algorithm for recognizing arc incidence graphs and reconstructing a graph with no isolated vertices from its arc incidence graph.     

A Sufficient Condition for a Graph to Have a k-tree

 A k-tree of a connected graph is a spanning tree with maximum degree at most k. We obtain a sufficient condition for a graph to have a k-tree, as a generalization of the condition of E. Flandrin, H. A. Jung and H. Li [3] for traceability. We also extend early results of Y. Caro, I. Krasikov and Y. Roditty [2] and Min Aung and Aung Kyaw [4] for the maximal order of a tree with bounded maximum degree in a graph. Received: July 28, 1997 Final version received: April 13, 1998     

Common Tangents to Four Unit Balls in R 3

We answer a question of David Larman, by proving the following result. Any four unit balls in three-dimensional space, whose centers are not collinear, have at most twelve common tangent lines. This bound is tight. Received October 25, 1999, and in final form May 24, 2000. Online publication January 17, 2001.     

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

Treewidth of the Line Graph of a Complete Graph

In recent articles by Grohe and Marx, the treewidth of the line graph of a complete graph is a critical example—in a certain sense, every graph with large treewidth “contains” . However, the treewidth of was not determined exactly. We determine the exact treewidth of the line graph of a complete graph.     

Graph of a Nearring with Respect to an Ideal

We introduce a concept called the graph of a nearring N with respect to an ideal I of N denoted by G _I (N). Then we define a new type of symmetry called ideal symmetry of G _I (N). The ideal symmetry of G _I (N) implies the symmetry determined by the automorphism group of G _I (N). We prove that if I is a 3-prime ideal of a zero-symmetric nearring N then G _I (N) is ideal symmetric. Under certain conditions, we find that if G _I (N) is ideal symmetric then I is 3-prime. Finally, we deduce that if N is an equiprime nearring then the prime graph of N is ideal symmetric.     

New Local Conditions for a Graph to be Hamiltonian

For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M₂(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)≥|M₂(w)|−1 for every induced path uwv. Then either G is hamiltonian or for some p≥2 where ∨ denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and for each vertex w of G. Supported by the Swedish Research Council (VR)     

Nonconstructible Simplicial Balls and a Way of Testing Constructibility

Constructibility of simplicial complexes is a notion weaker than shellability. It is known that shellable pseudomanifolds are homeomorphic to balls or spheres but simplicial complexes homeomorphic to balls or spheres need not be shellable in general. Constructible pseudomanifolds are also homeomorphic to balls or spheres, but the existence of nonconstructible balls was not known. In this paper we study the constructibility of some nonshellable balls and show that some of them are not constructible, either. Moreover, we give a necessary and sufficient condition for the constructibility of three-dimensional simplicial balls, whose vertices are all on the boundary. Received September 29, 1997, and in revised form August 3, 1998 and August 11, 1998.     

Covering Planar Graphs with a Fixed Number of Balls

In this note we prove that there exists a constant ρ such that any planar graph G of diameter ≤ 2R can be covered with at most ρ balls of radius R, a result conjectured by Gavoille, Peleg, Raspaud, and Sopena in 2001.     

Untangling a Planar Graph

A straight-line drawing δ of a planar graph G need not be plane but can be made so by untangling it, that is, by moving some of the vertices of G. Let shift(G,δ) denote the minimum number of vertices that need to be moved to untangle δ. We show that shift(G,δ) is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix(G,δ)=n?shift(G,δ) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling δ. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log\log n}$ vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ _G of G with $\ensuremath {\mathrm {fix}}(G,\delta_{G})\leq \sqrt{n-2}+1$ and an n-vertex outerplanar graph H and a drawing δ _H of H with $\ensuremath {\mathrm {fix}}(H,\delta_{H})\leq2\sqrt{n-1}+1$ . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

   Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.