A-Spectra and Q-Spectra of Two Classes of Corona Graphs

It is well known that graph spectra store a lot of structural information about a graph,and it is more difficult to compute the spectra of corona graphs. In this paper two classes of new corona graphs,the corona-vertex of the subdivision graph G1◇G2and corona-edge of the subdivision graph G1☆G2were defined. Then,by using the coronal of a graph and some knowledge of linear algebra,the adjacency spectra and the signless Laplacian spectra of the two new graphs were explicitly computed in terms of the corresponding spectra of G1 and G2. As the application,some Aintegral graphs were constructed.     

K-vertex-connectivity minimum augmentation for undirected unweighted graphs

For an undirected unweighted graph G0＝(V0,E0) and a positive integer K, the K-vertex-connectivity minimum augmentation problem (K-VCMAP) is to find a minimum set of edges Emin such that the graph H0＝(V0,E0∪Emin) is K-vertex-connected. Results in the literature have given polynomial time algorithms for K-VCMAP in several special cases such as where k≤3, or G0 is a tree. However, it still remains open whether or not there exist polynomial time algorithms for K-VCMAP for any graph G0 and any integer K. In this paper, we settle the problem by describing an efficient algorithm (KUCA) with time-complexity of O(K|V(G0)|5) for the K-VCMAP for any G0 and any positive integer K.     

Spectral Radius of Hamiltonian Planar Graphs and Outerplanar Graphs

All graphs considered here are finiteundirected,without loops and multiple edges.LetG be a graph with n verticesand m edges,d G( v) bethe degree of the vertex v in G,and Cn and Pn bethe cycle and path with n vertices. Thecomplement of a subgraph Y of G is the graphobtained from G by deleting all the edges in Y andis denoted by YG.The spectral radius r( G) of G isthe largest eigenvalue of its adjacent matrix.Aplanar graph G is called a maximal planar graph iffor every pairof nonadjacent…     

Antimagic Graphs with Even Factors

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2,……, E(G) }, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than 2K is antimagic. In this paper, we show that some graphs with even factors are antimagic, which generalizes some known results.     

A new class of antimagic join graphs

A labeling/of a graph G is a bijection from its edge set E(G) to the set {1,2,…,|E(G)|},which is antimagic if for any distinct vertices x anAy,the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y.A graph G is antimagic if G has an f which is antimagic.Hartsfield and Ringel conjectured in 1990 that every connected graph other than K_2 is antimagic.In this paper,we show that if G_1 is an m-vertex graph with maximum degree at most 6r+l,and G_2 is an n-vertex(2r)-regular graph(m≥n≥3),then the join graph G_1 v G_2 is antimagic.     

Some classes of disconnected antimagic graphs and their joins

A labeling of a graph G is a bijection from E(G) to the set {1,2,…,|E (G)| }.A labeling is antimagic if for any distinct vertices x and y,the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y.We say that a graph is antimagic if it has an antimagic labeling.Hartsfield and Ringel conjectured in 1990 that every graph other than 2 K is antimagic.In this paper,we show that the antimagic conjecture is false for the case of disconnected graphs.Furthermore,we find some classes of disconnected graphs that are antimagic and some classes of graphs whose complement are disconnected are antimagic.     

Almost every graph has a fixed edge

An edge e of a graph G is called a fixed edge if G-e+e′ G implies e′=e, and an isomorphic fixed edge if G-e+e′ G implies that there exists an automorphism of G-e, which maps the ends of e to the ends of e′. It is proved that almost every graph is with all its edges as fixed edges and isomorphic fixed edges, and it is conjectured that all graphs contain isomorphic fixed edges.     

Generalized Competition Indices of Primitive θ-Graphs

As a generalization of the scrambling index and the exponent,m-competition index has been widely applied to stochastic matrices,food webs and memoryless communication systems in recent years. For a positive integer m,where 1 ≤ m ≤ n,the mcompetition index( generalized competition index) of a primitive digraph D of order n is the smallest positive integer k such that for every pair of vertices x and y,there exist m distinct vertices v_1,v_2,…,v_m such that there exist walks of length k from x to v_i and from y to v_i for 1 ≤ i ≤ m. By analyzing the structure of θ-graphs( theta graphs) and using enumeration investigation methods,the mcompetition indices of primitive θ-graphs are studied and an upper bound is provided. Moreover, some corresponding extremal θ-graphs are characterized.     

Essential Independent Condition for Graphs to Be Hamiltonian

Let G be a graph of order n．For graph to be Hamiltonian,beginning with Dirac’s classic result in １９５２,Dirac’s theorem was followed by that of Ore in１９６０．In１９８４,Fan generalized Dirac’s theorem and Ore’s theorem as if G is a２-connected graph of order n and max｛d（u）,d（v）｝≥n/２for each pair of vertices u and v with d（u,v）＝２,then G is hamiltonian．In１９９１,Faudree et al proved that if G is a２-connected graph and,| N（u）∪N（v）|＋δ（G）≥n for each pair of nonadjacent vertices u,v∈V（G）,then G is hamiltonian．This paper generalizes the above onditions of Dirac,Ore,Fan and Faudree et al in the case of３-connected graph and proves that if G is a３-connected graph of order n and max｛｜N（x）∪ N（y）｜＋d（u）,｜N（w）∪N（z）｜＋d（v）｝≥n for every choice of６Essential independent vertices,then G is hamiltonian．     

Extracting multiple layers from data having graph structures

Much data such as geometric image data and drawings have graph structures. Such data are called graph structured data. In order to manage efficiently such graph structured data, we need to analyze and abstract graph structures of such data. The purpose of this paper is to find knowledge representations which indicate plural abstractions of graph structured data. Firstly, we introduce a term graph as a graph pattern having structural variables, and a substitution over term graphs which is graph rewriting system. Next, for a graph G, we define a multiple layer (g, (θ1,…,θk)) of G as a pair of a term graph g and a list of k substitutions θ1,…,θk such that G can be obtained from g by applying substitutions θ1…,θk to g. In the same way, for a set S of graphs, we also define a multiple layer for S as a pair (D,Θ) of a set D of term graphs and a list Θ of substitutions. Secondly, for a graph G and a set S of graphs, we present effective algorithms for extracting minimal multiple layers of G and S which give us stratifying abstractions of G and S, respectively. Finally, we report experimental results obtained by applying our algorithms to both artificial data and drawings of power plants which are real world data.     

Algorithm of graph isomorphism with three dimensional DNA graph structures

An algorithm for solving the graph isomorphism problem with 3-D DNA structures is proposed in this paper. The karmed branched junction molecules are used to code k-degree vertices. Double stranded molecules are used to code edges. Then the molecules are mixed in a tube to be ligated. The result can be detected by gel electrophoresis. The time complexity of the algorithm is O(n2), where n is the number of vertices of the graph.     

图Aα的矩阵的最小特征值的刻画

The unique graph which minimizes λ(A_α(G )) among all blocks with even number is determined. Some new bounds on λ(A_α(G )) in terms of the clique number, minimum degree and numbers of edges are also given.     

H-Magic and H-Supermagic of Graphs

An H-covering(resp.decomposition) of a graph G is a set of subgraphs of G,{H_1,H_2,…,H_k} such that H_1 is isomorphic to H for eachi,and each edge of G belongs to at least(resp.exactly) one of the subgraphs H_i,fox 1≤i≤k.An H-covering(resp.decomposition) of a graph G is a magic H-covering(resp.decomposition) if there is a bijection f:V(G)∪E(G)→{1,...,|V(G)|+|E(G)|} such that the sum of labels of edges and the vertices of each copy of H in the decomposition is a constant.If G admits a unique H-covering H and H is a magic H-covering of G,then G is H-magic.In this paper,we show that if G admits a magic H-covering(resp.decomposition),and satisfies some other conditions,then a union of k vertex joint graph G,kG,and a graph obtained from kG,Gk admit a magic H-covering or decomposition.     

Extracting multiple layers from data having graph structures

Much data such as geometric image data and drawings have graph structures. Such data are called graph structured data. In order to manage efficiently such graph structured data, we need to analyze and abstract graph structures of such data. The purpose of this paper is to find knowledge representations which indicate plural abstractions of graph structured data. Firstly, we introduce a term graph as a graph pattern having structural variables,and a substitution over term graphs which is graph rewriting system. Next,for a graph G,we define a multiple layer (g,（θ1, …,θk)) of G as a pair of a term graph g and a list of 4 substitutionsθ1, …,θk such that G can be obtained from g by applying substitutions θ1, …,θk to g. In the same way,for a set S of graphs, we also define a multiple layer for Sas a pair (D,@) of a set 5 of term graphs and a list 6 of substitutions. Secondly,for a graph G and a set S of graphs,we present effective algorithms for extracting minimal multiple layers of G and S which give us stratifying abstractions of G and S,respectively. Finally,we report experimental results obtained by applying our algorithms to both artificial data and drawings of power plants which are real world data.     

On k-Star Arboricity of Graphs

A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k ＋ 1. The k-star arboricity of a graph G,denoted by sak（ G）,is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2（ G） ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T）/k]t≤ sak（ T） ≤[Δ（ T）- 1/K]＋1,where Δ（ T） is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak（ T） ≤m for any tree T and any positive integers m and k.     

Fast algorithm for inverting structure parameters of the horizontal multi-layer soil

A fast algorithm is presented to invert the structure parameter of the horizontal multi-layer soil. The procedure is divided into two independent stages. First, Fredholm equation of the first kind with respect to the apparent resistivity is solved by the technology of decay spectrum to reduce computation time greatly. Second, the structure parameter of soil is determined by the generalized Newton-Kantorovich method, which is more robust and less noise sensitive because of using the generalized inverse algorithm to solve the nonlinear equation group. The numerical results show the validities and main features of the proposed approach.     

Extremal problem with respect to merrifield-simmons index and hosoya index of a class of polygonal chains

The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Ho- soya index of a graph is defined as the total number of the match- ings of the graph. In this paper, the definition of a class of po- lygonal chains is given, ordering of the polygonal chains with respect to Merrifield-Simmons index and Hosoya index are ob- tained, and their extremal graphs with respect to these two topo- logical indices are determined.     

A Worst-case execution time analysis approach based on independent paths for ARM programs

To overcome disadvantages of traditional worst-case execution time (WCET) analysis approaches, we propose a new WCET analysis approach based on independent paths for ARM programs. Based on the results of program flow analysis, it reduces and partitions the control flow graph of the program and obtains a directed graph. Using linear combinations of independent paths of the directed graph, a set of feasible paths can be generated that gives complete coverage in terms of the program paths considered. Their timing measurements and execution counts of program segments are derived from a limited number of measurements of an instrumented version of the program. After the timing measurement of the feasible paths are linearly expressed by the execution times of program seg-ments, a system of equations is derived as a constraint problem, from which we can obtain the execution times of program segments. By assigning the execution times of program segments to weights of edges in the directed graph, the WCET estimate can be calculated on the basis of graph-theoretical techniques. Comparing our WCET estimate with the WCET measurement obtained by the exhaustive measurement, the maximum error ratio is only 8.259 3 %. It is shown that the proposed approach is an effective way to obtain the safe and tight WCET estimate for ARM programs.     

An Efficient Algorithm for Discovering Co-occurrence Concepts Through Pathfinder Paradigm

The Pathfinder paradigm has been used in generating and analyzing graph models that support clustering similar concepts and minimum-cost paths to provide an associative network structure within a domain. The co-occurrence pathfinder network （ CPFN ） extends the traditional pathfinder paradigm so that co-occurring concepts can be calculated at each sampling time. Existing algorithms take O（n（s）） time to calculate the pathfinder network （PFN） at each sampling time for a non-completed input graph of a CPFN （r = ∞, q = n - 1）, where n is the number of nodes in the input graph, r is the Minkowski exponent and q is the maximum number of links considered in finding a minimum cost path between vertices. To reduce the complexity of calculating the CPFN, we propose a greedy based algorithm, MEC（G） algorithm, which takes shortcuts to avoid unnecessary steps in the existing algorithms, to correctly calculate a CPFN （r = ∞, q= n - 1） in O（klogk） time where k is the number of edges of the input graph. Our example demonstrates the efficiency and correctness of the proposed MEC（G） algorithm, confirming our mathematic analysis on this algorithm.     

Saturation Number for Linear Forest 2P_3∪tP_2

For a fixed graph F,a graph G is F-saturated if it has no F as a subgraph,but does contain F after the addition of any new edge.The saturation number,sat(n,F),is the minimum number of edges of a graph in the set of all F-saturated graphs with order n.In this paper,we determine the saturation number sat(n,2 P_3∪tP_2)and characterize the extremal graphs for n≥6 t+8.