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 .
20988039
Two conjectures equivalent to the perfect graph conjecture
Abstract In this note, we study the graphs with the property that each of their induced subgraphs has circular clique number (defined in Section 2) the same as its clique number, prove that a graph satisfies such a property if and only if neither itself nor its complement contains an induced subgraph isomorphic to an odd cycle of length at least five, and then give two conjectures which are equivalent to the perfect graph conjecture.
37647794
On 3-colorable plane graphs without 5- and 7-cycles
In this note, it is proved that every plane graph without 5- and 7-cycles and without adjacent triangles is 3-colorable. This improves the result of [O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B 93 (2005) 303-311], and offers a partial solution for a conjecture of Borodin and Raspaud [O.V. Borodin, A. Raspaud, A sufficient condition for planar graphs to be 3-colorable, J. Combin. Theory Ser. B 88 (2003) 17-27].
37612124
Minimally circular-imperfect graphs with a major vertex
In this note, we characterize the minimally circular-imperfect graphs that have a major vertex.
12925025
The 4-Choosability of Plane Graphs without 4-Cycles'
A graphGis calledk-choosable ifkis a number such that if we give lists ofkcolors to each vertex ofGthere is a vertex coloring ofGwhere each vertex receives a color from its own list no matter what the lists are. In this paper, it is shown that each plane graph without 4-cycles is 4-choosable.
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.
39744832
On signed edge domination numbers of graphs
Abstract Given a graph G=(V,E) , if e=uv∈E , then the closed edge-neighbourhood of e is denoted by N[e]={u′v′∈E|u′=u or v′=v} . A function f : E→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑ e′∈N[e] f(e′)⩾1 for every e∈E . The signed edge domination number γ s ′(G) of G is defined as γ s ′(G)= min {∑ e∈E f(e) | f is an SEDF of G} . Let Ψ(m)= min {γ s ′(H)|H is a graph with |E(H)|=m} . In this paper, we determine the exact value of Ψ(m) for each positive integer m . That is: Ψ(m)=2 1 3 24m+25 +6m+5 6 −m, where ⌈x⌉ denotes the ceiling of x . In addition, we also characterize all connected graphs G with γ s ′(G)=|E(G)| .
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.
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.
32570723
Parallel algorithm for mining fuzzy association rules
The principle and steps of the algorithm for mining fuzzy association rules is studied, and the parallel algorithm for mining fuzzy association rules is presented. In this parallel mining algorithm, quantitative attributes are partitioned into several fuzzy sets by the parallel fuzzy c-means algorithm, and fuzzy sets are applied to soften the partition boundary of the attributes. Then, the parallel algorithm for mining Boolean association rules is improved to discover frequent fuzzy attributes. Last, the fuzzy association rules with at least fuzzy confidence are generated on all processors. The parallel mining algorithm is implemented on the distributed linked PC/workstation. The experiment results show that the parallel mining algorithm has fine scaleup, sizeup and speedup.
31813405
Website evolution based on statistic data
Maintenance and evolution are critical for website since the requirements often change, the developing cycle is short, while the life cycle is long. In order to make progress in this area, we focus on the users' responses and attitudes. So we begin our work at the log files on the side of website server, gathering the users' visiting information and the server's responses. Thus we obtain our weighted structure model. Then, we analyze and discuss such information to identify the key pages, the predominate pages and the users' visiting patterns. And we can improve the testing efficiency based on these knowledge. All these will help to improve the structure of the site, fulfill the functionality of the site, and enhance users' visiting efficiency.