24192218
On point-linear arboricity of planar graphs
The point-linear arboricity of a graph G=(V, E), written as p 0 (G), is defined as p 0 (G)=min{k | there exists a partition of V into k subsets, V=∪=1 V i such that (V i ) is a linear forest for 1 >i>k}. In this paper, we will discuss the point-linear arboricity of planar graphs and obtained following results: p 0 (G)=2 if G is a outplanar graph. p 0 (G)=4 if G is a planar graph.
17919993
A Note on the Edge-Connectivity of Cages
A (k; g)-graph is a k-regular graph with girth g. A (k; g)-cage is a (k; g)-graph with the smallest possible number of vertices. In this paper we prove that (k; g)cages are k-edge-connected if k ≥ 3 and g is odd.
37643061
Adjacent strong edge coloring of graphs
Abstract For a graph G ( V , E ), if a proper k -edge coloring ƒ is satisfied with C ( u ) ≠ C ( v ) for uv ∈ E ( G ), where C(u) = {ƒ(uv) | uv ∈ E} , then ƒ is called k-adjacent strong edge coloring of G , is abbreviated k-ASEC , and χ ′ as ( G ) = min { k | k - ASEC of G } is called the adjacent strong edge chromatic number of G . In this paper, we discuss some properties of χ′ as ( G ), and obtain the χ′ as ( G ) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ ′ as ( G ) ≤ Δ ( G ) + 2, where Δ( G ) is the maximum degree of G .
31774377
Factors in graphs with odd-cycle property
Abstract We present some conditions for the existence of a ( g , f )-factor or a ( g , f )-parity factor in a graph G with the odd-cycle property that any two odd cycles of G either have a vertex in common or are joined by an edge.
6641485
On total covers of graphs
A total cover of a graph G is a subset of V(G)∪E(G) which covers all elements of V(G)∪E(G). The total covering number α2(G) of a graph G is the minimum cardinality of a total cover in G. In [1], it is proven that α2(G)⩽[n2] for a connected graph G of order n. Here we consider the extremal case and give some properties of connected graphs which have a total covering number [n2]. We prove that such a graph with even order has a 1-factor and such a graph with odd order is factor-critical.
206571042
An Upper Bound for the Independent Domination Number
Let G be a simple graph of order n and minimum degree ?. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. In this paper, we show that i(G)?n+2??2n?. Thus a conjecture of Favaron is settled in the affirmative.
7700079
On 1-Arc-regular Graphs
A graph is 1-arc-regular if its full automorphism group acts regularly on the set of its arcs. In this paper, we investigate 1-arc-regular graphs of prime valency, especially of valency 3. First, we prove that if G is a soluble group then a (G, 1)-arc-regular graph must be a Cayley graph of a subgroup of G. Next we consider trivalent Cayley graphs of a finite nonabelian simple group and obtain a sufficient condition under which one can guarantee that Cay(G, S) is 1-arc-regular. Finally, as an application of the result, we construct two infinite families of 1-arc-regular trivalent Cayley graphs with insoluble automorphism groups and, in particular, one of the families is not a Cayley graph.
8350188
Constraint Propagation And Progressive Verification For Component-Based Process Model
System assembly is one of the major issues in engineering complex component-based systems. This is especially true when heterogeneous, COTS and GOTS distributed systems, typical in industrial applications, are involved. The goal of system assembly is not only to make constituent components work together, but also to ensure that the components as a whole behave consistently and guarantee certain end-to-end properties. Despite recent advances, there is a lack of understanding about software composability, as well as theory and techniques for checking and verifying component-based systems. A theory of software system constraints about components, their environment and about system as a whole is the necessary foundation toward solid understanding of the composability of component-based systems. In this paper, we present a systematic approach for constraint specification and constraint propagation in concert with design refinement with a novel technique to ensure consistency between system-wide and component constraints in a design composition process of component-based systems. The consistent constraint propagation is used in our approach to drive progressive verification of the design. It allows us to verify overall design composition without interference of internal details of component designs. Verification is done separately at architectural and component levels without having to compose results of component analyses. A component can be safely replaced with alternative design without re-verifying the overall system composition so long as the replacement conforms to the corresponding interface and component constraint(s).
205093793
On p-Creative Sets and p-Completely Creative Sets
Abstract We study p-creative sets and p-completely creative sets. We first prove that for recursively enumerable sets, p-creativeness is equivalent to p-complete creativeness and Myhill's theorem still holds in the polynomial setting. We then consider p-creativity and p-complete creativity for time complexity classes. We prove that for P, p-creativeness is equivalent to p-complete creativeness. Moreover, we prove that a set A is p-m-complete for DEXT iff A is p-creative for P in DEXT. Since every p-m-complete set for DEXT is p-1-complete (Berman, 1977), we know that Myhill's theorem still holds for P in DEXT. These results can also be proved for NP in NEXT. k -creative sets and k -completely creative sets in NP are next studied. ( k,l )-creative sets and ( k,l )-completely creative sets in a more general setting are defined and shown to exist. It is known that k -completely creative sets are NP-complete (Joseph and Young, 1985), but it is not known whether the converse is true. We approach this problem based on our “double diagonalization” technique of showing that every p-m-complete set for DEXT is p-creative for P. A new class of k -completely creative sets is constructed as well.
1667264
Path extendability of claw-free graphs
Let G be a connected, locally connected, claw-free graph of order n and x,y be two vertices of G. In this paper, we prove that if for any 2-cut S of G, S@?{x,y}=@A, then each (x,y)-path of length less than n-1 in G is extendable, that is, for any path P joining x and y of length h(
11808205
Mending broken handwriting with a macrostructure analysis method to improve recognition
Abstract Broken characters always create problems in handwriting recognition systems, especially those using boundary and/or skeleton information. This paper presents a macrostructure analysis (MSA) mending method based on skeleton and boundary information and an MSA that investigates the stroke tending direction and other properties of handwritings. A new skeleton end extension algorithm is introduced, which compensates the defectiveness of the skeletonization algorithm and obtains a satisfactory skeleton. When combined with suitable parameters, improved performance from a handwriting classifier is achieved. The experimental results from over 13 000 numerals show the efficiency and robustness of the proposed method, raising recognition rates by over 10% for broken handwritten digits, from 74.8% to 86.4%.