11402970
On structure of graphs embedded on surfaces of nonnegative characteristic with application to choosability
In this paper, we prove a structural theorem of Lebesgue's type concerning some unavoidable configurations for graphs which can be embedded on surfaces of nonnegative characteristic and in which no two 3-cycles share a common vertex. As a corollary, we get a result about choosability of graphs embedded in surface of positive characteristic.
30431957
On endo-homology of complexes of graphs
Abstract Let L be a subcomplex of a complex K . If the homomorphism from inclusion i ∗ :H q (L)→H q (K) is an isomorphism for all q ⩾ 0, then we say that L and K are endo-homologous. The clique complex of a graph G , denoted by C ( G ), is an abstract complex whose simplices are the cliques of G . The present paper is a generalization of Ivashchenko (1994) along several directions. For a graph G and a given subgraph F of G , some necessary and sufficient conditions for C ( G ) to be endo-homologous to C ( F ) are given. Similar theorems hold also for the independence complex I ( G ) of G , where I ( G ) − C ( G c ), the clique complex of the complement of G .
30641096
On the fixed edge of planar graphs with minimum degree five
Abstract An edge e of a finite and simple graph G is called a fixed edge of G if G - e + e ′ ≅ G implies e ′ = e . In this paper, we show that planar graphs with minimum degree 5 contain fixed edges, from which we prove that a class of planar graphs with minimum degree one is edge reconstructible.
16379968
On Structure of Some Plane Graphs with Application to Choosability
A graph G=(V, E) is (x, y)-choosable for integers xy?1 if for any given family {A(v)?v?V} of sets A(v) of cardinality x, there exists a collection {B(v)?v?V} of subsets B(v)?A(v) of cardinality y such that B(u)?B(v)=? whenever uv?E(G). In this paper, structures of some plane graphs, including plane graphs with minimum degree 4, are studied. Using these results, we may show that if G is free of k-cycles for some k?{3, 4, 5, 6}, or if any two triangles in G have distance at least 2, then G is (4m, m)-choosable for all nonnegative integers m. When m=1, (4m, m)-choosable is simply 4-choosable. So these conditions are also sufficient for a plane graph to be 4-choosable.
37612124
Minimally circular-imperfect graphs with a major vertex
In this note, we characterize the minimally circular-imperfect graphs that have a major vertex.
7708894
Decomposing toroidal graphs into circuits and edges
Erdos et al. (Canad. J. Math. 18 (1966) 106-112) conjecture that there exists a constant d"c"e such that every simple graph on n vertices can be decomposed into at most d"c"en circuits and edges. We consider toroidal graphs, where the graphs can be embedded on the torus, and give a polynomial time algorithm to decompose the edge set of an even toroidal graph on n vertices into at most (n+3)/2 circuits. As a corollary, we get a polynomial time algorithm to decompose the edge set of a toroidal graph (not necessarily even) on n vertices into at most 3(n-1)/2 circuits and edges. This settles the conjecture for toroidal graphs.
30598486
Regression testing for Web applications based on slicing
Web applications have rapid developing speed and changeable user demands, so the regression testing is much important. Since the changed demands result in different versions of Web applications, and the faults usually hiding in the adjusted contents, the regression testing must cover all the related pages. In order to carry through the regression testing quickly and effectively, we make the simplification with the method of slicing. Firstly, we analyze the possible changes in the Web applications and the influences produced by these changes, discussing in the direct-dependent and indirect-dependent way; next, we give the regression testing method based on slicing emphasized on the indirect-dependent among data, i.e., obtaining the dependent set of changed variables by forward and backward search method and generating the testing suits; conclusion remarks and future work are given at last.
38400231
On mixed Ramsey numbers
Abstract For a graph theoretic parameter f , an integer m and a graph H , the mixed Ramsey number v(f; m; H) is defined as the least positive integer p such that if G is any graph of order p , then either f(G) ⩾ m or Ḡ contains a subgraph isomorphic to H . Let ϱ denote vertex linear arboricity and let H be any connected graph of order n . In this note we show that v(ϱ; m; H) = 1 + (n + n p ( H ) − 2)(m − 1) , where n p ( H ) is the path partition number of H .
28979330
Connected Factors and Spanning Trees in Graphs
Abstract. Let G be a graph, and g, f, f′ be positive integer-valued functions defined on V(G). If an f′-factor of G is a spanning tree, we say that it is f′-tree. In this paper, it is shown that G contains a connected (g, f+f′−1)-factor if G has a (g, f)-factor and an f′-tree.
29802636
Two classes of edge domination in graphs
Let γ's(G) (γ'l(G), resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that γ's(G) ≤ ⌊11/6n - 1⌋ and γ's(G) ≤ 2n - 4 hold for any graph G of order n (n ≥ 4), and pose several open problems and conjectures.
18072223
Mining association rules with linguistic terms
Some problems of mining association rules with linguistic terms are discussed. First, an incremental updating algorithm of association rules with linguistic terms is presented. The collection of frequent linguistic attribute sets and its negative border along with their support count are maintained, which makes scan the entire database once at most in the process of updating association rules. The experiment shows that the updating algorithm can not only update association rules effectively but also avoid the repeated cost. Secondly, the parallel algorithm for mining association rules with linguistic terms is presented. The Boolean parallel mining algorithm is improved to discover frequent linguistic attribute sets, and the association rules with at least confidence are generated on all processors. This parallel mining algorithm has fine scale-up, size-up and speed-up.