13307767
A note on acyclic domination number in graphs of diameter two
A subset S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by @c"a(G), is called the acyclic domination number of G. Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151-165] introduced the concept of acyclic domination and posed the following open problem: if @d(G) is the minimum degree of G, is @c"a(G)= =k.
4357183
A New Proof of Wojcicka's Conjecture
A graph G is 3-domination-critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Wojcicka conjectured that every 3-domination-critical graph with δ ≥ 2 has a hamiltonian cycle (J. Graph Theory 14 (1990) 205-215). The conjecture had been proved and its proof consists of two parts: the case α ≤ δ + 1 (J. Graph Theory 25 (1997) 173-184) and the case α = δ + 2 (Discrete Appl. Math. 92 (1999) 57-70). In this paper, we give a new and simple proof of the conjecture by using Hanson's (J. Combin. Math. Combin. Comput. 13 (1993) 121-128) and Bondy-Chvatal's (Discrete Math. 15(1976) 111-135) closure operations.
15445426
An Ore-type Condition for Cyclability
A graph G is said to be cyclable if for each orientation D of G, there exists a set S(D) ?V(G) such that reversing all the arcs with one end in S results in a Hamiltonian digraph. Let G be a simple graph of even ordern? 8. In this paper, we show that if the degree sum of any two nonadjacent vertices is not less thann+ 1, then G is cyclable and the lower bound is sharp.
6176366
The Ramsey numbers of stars versus wheels
For two given graphs G 1 and G 2 , the Ramsey number R(G 1 , G 2 ) is the smallest positive integer n such that for any graph G of order n, either G contains G 1 or the complement of G contains G 2 . Let S n denote a star of order n and W m a wheel of order m + 1. This paper shows that R(S n , W 6 )=2n + 1 for n ≥ 3 and R(S n , W m )=3n - 2 for m odd and n ≥ m - 1 ≥ 2.
206858542
Degree Sums and Path-Factors in Graphs
Abstract. Let G be a connected graph of order n and suppose that n=∑i=1kni, where ni≥2 are integers. In this paper we give some sufficient conditions in terms of degree sums to ensure that G contains a spanning subgraph consisting of vertex disjoint paths of orders n1,n2,…,nk.
12956058
Identifying meaningful return information for XML keyword search
Keyword search enables web users to easily access XML data without the need to learn a structured query language and to study possibly complex data schemas. Existing work has addressed the problem of selecting qualified data nodes that match keywords and connecting them in a meaningful way, in the spirit of inferring a where clause in XQuery. However, how to infer the return clause for keyword search is an open problem.
 To address this challenge, we present an XML keyword search engine, XSeek, to infer the semantics of the search and identify return nodes effectively. XSeek recognizes possible entities and attributes inherently represented in the data. It also distinguishes between search predicates and return specifications in the keywords. Then based on the analysis of both XML data structures and keyword match patterns, XSeek generates return nodes. Extensive experimental studies show the effectiveness of XSeek.
16940810
Vertex and Tree Arboricities of Graphs
This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.
6014524
Physically-based animation of volumetric objects
The paper presents a voxel-based animation technique which employs either a mass-spring model or a finite element model. Two volumetric objects, a voxelized chair and a scanned muscle, are used as case studies with the two different models. The mass-spring model is used to show an animation sequence of a falling and bouncing chair: wireframe display and volume rendering are used to display a real-time animation of the process. In addition, a real-time simulation is carried out by the finite element method (FEM) of a voxel-based multi-resolution muscle mesh. Two techniques, a direct integration and a simplified modal analysis method are discussed in the context of applying FEM for muscle deformation. Local deformation optimization with modal analysis for higher resolution muscle volumetric animation, which allows accurate prediction of muscle deformation changes, has been used. Physiological muscle force has been considered and a biomechanically-based 3D FEM muscle model has been implemented. Realistic animations have been produced based on the FEM simulation with various graphics techniques.
33065239
Triangle-free Hamiltonian Kneser graphs
The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2,...,n}. Two vertices are adjacent if the k-sets are disjoint. When n > 3k, the Kneser Graph K(n, k) has no triangle. In this paper, we prove that K(n,k) is Hamiltonian for n ≥ (3k + 1 + √5k2- 2k + 1)/2, and extend this to the bipartite Kneser graphs. Note that (3k + 1 + √5k2 - 2k + 1)/2 > 2.62k + 1.
16469592
IT businesses and franchising: a research proposal
Franchising has been popular as a growth strategy for small businesses; it is even more so in today's global and information-based economy. In early 2001, Entrepreneur magazine-well known for its Franchise 500 listing-added a tech businesses category to its franchise zone with three subcategories: Internet businesses, tech training, and miscellaneous tech businesses. This study applies Herbert Simon's model for business firm growth as a theory-grounded solution to help managers understand the growth dynamics of IT-based franchising businesses. We present a research proposal with a pilot study of the growth of 27 IT-based franchise businesses, and explain how to relate the parameters of Simon's model to strategic variables that can give managers a valuable strategic tool to understand the context of their industrial competition in IT-based franchising.