On the Maximum Matching Graph of a Graph

1IntroductionMatchingtheory,aswellastheassignmentprobleminlinearprogramming,hasawiderangeofapplicationinthetheoryandpracticeofoperationsresearch.Bysomepracticalmotivations,e.g.,forfindingalloptimalsolutions,peoplewanttoknowthestructurepropertiesofallmaximummatchingsofagraphG.InthecasethatGhasperfectmatchings,extensiveworkhasbeendoneontheso-calledperfectmatChinggrape(or1-factorgraph),inwhichtwoperfectmatchingsMIandMZaresaidtobeadjacentifMI~MZ@E(C)whereCisanMI-alternatingcycleofG.Therewer…     

When is the Comaximal Graph Split?

Let R be a commutative ring with non zero unity. Let Ω(R) be a graph with vertices as elements of R whose two distinct vertices x and y are adjacent if and only if Rx + Ry = R. A graph (V, E) is said to be a split graph if V is the disjoint union of two sets K and S where K induces a complete subgraph and S is an independent set. We investigate the properties of R when Ω(R) is split.     

A Note on the Graph of Class One

1 Introduction Let G be a simple graph. An edge colouring ∏ of G is a map ∏: E(G)→{1,2,…} such that no two adjacent edges have the same image. The chromatic index X' (G) of G is the minimum cardinality of all possible images of colouring of G. By Vizing's theorem if △ is the maximum degree of G.     

Induced Matching Number of the Plane Grid Graph

An induced matching M in a graph G is a matching such that V(M) induces a 1-regular subgraph of G. The induced matching number of a graph G, denoted by I M(G), is the maximum number r such that G has an induced matching of r edges. Induced matching number of Pm×Pn is investigated in this paper. The main results are as follows:(1) If at least one of m and n is even, then IM(Pm×Pn=[(mn)/4].(2) If m is odd, then     

On the Covering of the Vertices of a Graph by Cliques

In conversation I was told by Professor R.Brigham the following conjecture [1].Let G(n) be a graph of n vertices.Denote by f(G(n))=t the smallest integer for which the vertices of G(n) can be covered by t cliques. Denote further by h(G(n)) =l the largest integer for which there are l edges of our G(n) no two of Which are in the same clique.Clearly h(G(n)) can be much larger than f(G(n))e.g.if n=2m and G(n) is the complete bipartite graph of m white and m black vertices.Then l(G(n))=m and l(G(n))=m~2. It was conjectured that if G(n).has no isolated vertices then     

A Note on the Bondage Number of a Graph

ＡＮｏｔｅｏｎｔｈｅＢｏｎｄａｇｅＮｕｍｂｅｒｏｆａＧｒａｐｈ￥ＬｉＹｕｑｉａｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＧｕａｎｇｚｈｏｕＴｅａｃｈｅｒ＇ｓＣｏｌｌｅｇｅ）Ａｂｓｔｒａｃｔ：Ｔｈｅｂｏｎｄａｇｅｎｕｍｂｅｒｂ（Ｇ）ｏｆａｇ...     

Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

Inverse Problems for the Dirac Operator on a Star Graph

Following the previous work, we shall study some inverse problems for the Dirac operator on an equilateral star graph. It is proven that the so-called Weyl function uniquely determines the potentials. Furthermore, we pay attention to the inverse problem of recovering the potentials from the spectral data, which consists of the eigenvalues and weight matrices, and present a constructive algorithm. The basic tool in this paper is the method of spectral mappings developed by Yurko.     

Some Remarks on the Graph Γ I (R)

Let R be a commutative ring with nonzero identity and Z(R) its set of zero-divisors. The zero-divisor graph of R is Γ(R), with vertices Z(R)?{0} and distinct vertices x and y are adjacent if and only if xy = 0. For a proper ideal I of R, the ideal-based zero-divisor graph of R is Γ _I (R), with vertices {x ∈ R?I | xy ∈ I for some y ∈ R?I} and distinct vertices x and y are adjacent if and only if xy ∈ I. In this article, we study the relationship between the two graphs Γ(R) and Γ _I (R). We also determine when Γ _I (R) is either a complete graph or a complete bipartite graph and investigate when Γ _I (R) ? Γ(S) for some commutative ring S.     

On Primitive Idempotents of the Strong Endomorphism Monoid of a Graph

51.IntroductionandPreIiminariesThemonoidofendomorphismsofagraph,inparticular,thatofstrongendomorphismsofagraph,hasbeentheobjectofresearchesinthetheoryofsemigroupsforquitesometime(cf.Llj-Lloj).LlJandL2jcanserveasasurvey.Theaimoftheseresearchesistocon-tributetothealgebraicanalysisofgraphs.Thesubjectyieldssomeinterestsincetheresultsoftheseresearchesmayopenvastpossibilitiesforapplicationsofsemigrouptheorytographtheo-ry.InL1]andL3j,ithasbeenprovedthatforfinitegraphG,sEnd(G),themonoidofstrongen…     

Spectral Characterizations of the Lovász Number and the Delsarte Number of a Graph

This paper gives spectral characterizations of two closely related graph functions: the Lovász number and a generalization ¹ of Delsarte's linear programming bound. There are many known characterizations of the Lovász number , and each one corresponds to a similar characterization of ¹ obtained by extremizing over a larger or smaller class of objects.The spectral characterizations of and ¹ given here involve the largest eigenvalue of a type of weighted Laplacian that Fan Chung introduced.     

Graph homomorphisms,the Tutte polynomial and “q-state Potts uniqueness”

We establish for which weighted graphs H homomorphism functions from multigraphs G to H are specializations of the Tutte polynomial of G, answering a question of Freedman, Lovász and Schrijver.We introduce a new property of graphs called “q-state Potts uniqueness” and relate it to chromatic and Tutte uniqueness, and also to “chromatic–flow uniqueness”, recently studied by Duan, Wu and Yu.     

Graph algorithms for DNA sequencing – origins,current models and the future

With the ubiquitous presence of next-generation sequencing in modern biological, genetic, pharmaceutical and medical research, not everyone pays attention to the underlying computational methods. Even fewer researchers know what were the origins of the current models for DNA assembly. We present original graph models used in DNA sequencing by hybridization, discuss their properties and connections between them. We also explain how these graph models evolved to adapt to the characteristics of next-generation sequencing. Moreover, we present a practical comparison of state-of-the-art DNA de novo assembly tools representing these transformed models, i.e. overlap and decomposition-based graphs. Even though the competition is tough, some assemblers perform better and certainly large differences may be observed in hardware resources utilization. Finally, we outline the most important trends in the sequencing field, and try to predict their impact on the computational models in the future.     

What is a Graph?

In the past few years, the subject of graph theory (or network analysis) has come very much to the fore, not only as an important mathematical discipline in its own right, but also as a useful mathematical tool in a wide variety of subjects, ranging from organic chemistry and probability, through operational research and geography, to sociology and linguistics. In this article, we shall present some simple applications of graph theory, chosen in such a way as to be as elementary but as varied as possible. The reader who is interested in pursuing the subject further should consult Reference 1; for a lengthy account of some further applications of graph theory, see Chapter six of Reference 2.     

On the Uniqueness of the Solution of the Inverse Sturm–Liouville Problem with Nonseparated Boundary Conditions on a Geometric Graph

For the first time, the inverse Sturm–Liouville problem with nonseparated boundary conditions is studied on a star-shaped geometric graph with three edges. It is shown that the Sturm–Liouville problem with general boundary conditions cannot be uniquely reconstructed from four spectra. Nonseparated boundary conditions are found for which a uniqueness theorem for the solution of the inverse Sturm–Liouville problem is proved. The spectrum of the boundary value problem itself and the spectra of three auxiliary problems are used as reconstruction data. It is also shown that the Sturm–Liouville problem with these nonseparated boundary conditions can be uniquely recovered if three spectra of auxiliary problems are used as reconstruction data and only five of its eigenvalues are used instead of the entire spectrum of the problem.     

On the Gracefulness of Graph（jC_（4n））∪P_m

The present paper deals with the gracefulness of unconnected graph （jC_（4n））∪P_m,and proves the following result：for positive integers n,j and m with n≥1,j≥2,the unconnected graph（jC_（4n））∪P_m is a graceful graph for m=j-1 or m≥n＋j,where C_（4n） is a cycle with 4n vertexes,P_m is a path with m＋1 vertexes,and（jC_（4n））∪P_m denotes the disjoint union of j-C_（4n） and P_m.     

The Binding Number of a Graph

The binding number of a graph is an important characteristic quantity of agraph.In1973 Woodall first introduced the concept of the binding number ofa graph and then gave the binding number of some special graphs in[1].In1981 Kane,Mohanty and Hales gave the binding number of some product graphsin[2].Wang Jianfang,Tian Songlin,Liu Ziuqiang(1983-1987)gave the bin-ding number of some multi-product graphs,and it is the limit character.Up to     

Conjecture on Self Hamiltonian Path Graph

The Hamiltonian path graph H(G) of a graph G isa that graph having the samevertex set as G and in which two vertices u and v are adjacent if and only if Gcontains a Hamiltonian u - v path. A graph G is a self-Hamiltonian path graph ifG≌H(G).G. Chartrand conjecture: A graph G of order p is a self-Hamiltonian path:graph if and only if G is chord additive or G is isomorphic to one of the graphsK_p, (?)_p, C_p(p≥3),K((1/2)p, (1/2)p), and K_(p/2) (?)_(p/2),the last two for even P.