Reliability Analysis of the Cayley Graphs of Dihedral Groups

Cayley graphs have many good properties as models of communication networks.This study analyzes the reliability of the Cayley graph based on the dihedral graph.Graph theory and analyses show that almost all Cayley graphs of the dihedral graph D 2n are optimal super-λ.The number (G) i N of cutsets ofsize i,λ ≤i ≤λ' is given as Ni(G)=n((n-1)δ/i-δ).     

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-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.     

On the Spectral Moment of Quasi-Unicyclic Graphs

A connected graph G=(V(G),E(G)) is called a quasi-unicyclic graph,if there exists u_0∈V(G) such that G-u_0 is a unicyclic graph.Denote Q(n,d_0)={G:G is a quasi-unicyclic graph of order n with G-u_0 being a unicyclic graph and d_G(u_0)=d_0}.Let A(G) be the adjacency matrix of a graph G,and let λ_1(G),λ_2(G),…,λ_n(G) be the eigenvalues in non-increasing order of A(G).The number■(k=0,1,…,n-1) is called the k-th spectral moment of G,denoted by S_k(G).Let S(G)=(S_0(G),S_1(G),…,S_(n-1)(G)) be the sequence of spectral moments of G.For two graphs G_1,G_2,we have■ if for some k(k=1,2,…,n-1), and we have S_i(G_1)=S_i(G_2)(i=0,1,…,k-1) and S_k(G_1)S_k(G_2).In this paper,we determine the second to the fourth largest quasi-unicyclic graphs,in an S-order,in the set Q(n,d_0),respectively.     

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.     

The Further Results of the Chromatic Uniqueness of Certain Bipartite Graphs K （m,n）- A

With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.     

Design Pattern Mining Using Graph Matching

The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decom-posed into subgraphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs.     

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…     

2×n格子图的弱罗马控制数

图G弱罗马控制数是图G的所有弱罗马控制数(WRDF)的最小权.本文运用指标函数法和比较函数法确定了2×n 格子图的弱罗马控制数.

Abstract：

The weak Roman domination number of G is the minimum weight of a weak Roman dominating function (WRDF) in G. In this paper, we determine the weak Roman domination number of 2 × n grid graphs.     

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.     

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.     

Optimal parallel algorithm for shortest paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.     

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.     

The (Δ+2,2)-incidence coloring of outerplanar graphs

An incidence coloring of graph G is a coloring of its incidences in which neighborly incidences are assigned different colors. In this paper, the incidence coloring of outerplanar graphs is discussed using the techniques of exchanging colors and the double inductions from the aspect of configuration property. Results show that there exists a (Δ+2,2)-incidence coloring in every outerplanar graph, where Δis the maximum degree of outerplanar graph.     

The (Δ+2,2)-incidence coloring of outerplanar graphs

An incidence coloring of graph G is a coloring of its incidences in which neighborly incidences are assigned different colors. In this paper, the incidence coloring of outerplanar graphs is discussed using the techniques of exchanging colors and the double inductions from the aspect of configuration property. Results show that there exists a (Δ+2,2)-incidence coloring in every outerplanar graph, where Δis the maximum degree of outerplanar graph.     

The （△ ＋ 2,2）-incidence coloring of outerplanar graphs

An incidence coloring of graph G is a coloring of its incidences in which neighborly incidences are assigned different colors. In this paper, the incidence coloring of outerplanar graphs is discussed using the techniques of exchanging colors and the double inductions from the aspect of configuration property. Results show that there exists a （△ ＋ 2,2）-incidence coloring in every outerplanar graph, where A is the maximum degree of outerplanar graph.     

Causal Inference in Graph-Text Constellations:Designing Verbally Annotated Graphs

Multimodal documents combining language and graphs are wide-spread in print media as well as in electronic media.One of the most important tasks to be solved in comprehending graph-text combinations is construction of causal chains among the meaning entities provided by modalities.In this study we focus on the role of annotation position and shape of graph lines in simple line graphs on causal attributions concerning the event presented by the annotation and the processes (i.e.increases and decreases) and states (no-changes) in the domain value of the graphs presented by the process-lines and state-lines.Based on the experimental investigation of readers’ inferences under different conditions,guidelines for the design of multimodal documents including text and statistical information graphics are suggested.One suggestion is that the position and the number of verbal annotations should be selected appropriately,another is that the graph line smoothing should be done cautiously.     

The Total Irredundance Numbers on Graphs

This paper discusses the total irredundance relations between the graph G and its clone-contraction graph H, that is, let H be the clone-contraction graph of G and v1,v2,...,vk be all contraction vertices ofH. IfS is a maximal total irredundant set of H such that A = S ∩ {V1,V2,…,Vk} contains as few vertices as possible, then S＇= S-A is the maximal total irredundant set of G. Furthermore, we obtain the bound of the total irredundance A（G） number： irt ≤△（G）/2△（G）＋1 n, which n is the order of graph G, and △（G） is maximum degree in G.     

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.     

Binding number,minimum degree and bipancyclism in bipartite graphs

Let G =(V_1,V_2,E) be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B(G),is defined to be n if G =K_n and min i∈{1,2}|N(S)|n min |N(S)|/|S|otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B(G) 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows:Let 0 c 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n(n is large enough) vertices such that B(G) c and δ(G)(2-c)n/(3-c)+2/3.Then G is bipancyclic.