The product of the restrained domination numbers of a graph and its complement

Let G=(V,E) be a graph.A set S■V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S.The restrained domination number of G,denoted γr(G),is the smallest cardinality of a restrained dominating set of G.In this paper,we show that if G is a graph of order n≥4,then γr(G)γr(G)≤2n.We also characterize the graphs achieving the upper bound.     

A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs

A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in seriesparallel graphs and present a linear-time exact algorithm to solve it.     

On the spectral spread of bicyclic graphs with given girth

The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and |E(G)| = |V(G)|+ 1. Let B(n, g) be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B(n, g) is determined.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

Bounds on the clique-transversal number of regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.     

On the Clique-Transversal Number in （Claw,K4）-Free 4-Regular Graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC(G),is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC(G) and characterize the extremal graphs achieving the lower bound for a connected(claw,K4)-free 4-regular graph G.Furthermore,we show that for any 2-connected(claw,K4)-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].     

具有5n个点的完全5部图的分类及5图部的色性

§ 1　IntroductionAll graphs considered here are finite and simple.For notations and terminology notdefined here,we refer to [1].For a graph G,by V(G) and E(G) we mean the vertex- setand edge- setof G,respectively.By N3(G) we denote the number of triangles in G.L et S bea set of sedges in G.By G- S (or G- s) we denote the graph obtained from G by deletingall edges in S.L et K (n1 ,n2 ,...,nt) be a complete t- partite graph.We denote by K- sn1 ,n2 ,...,ntthe family of graphs which are …     

单圈图的极小能量

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un| d(x) = r for any vertex x ∈ V(Cl)}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39(2, 2, 2) ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.     

Regular and Maximal Graphs with Prescribed Tripartite Graph as a Star Complement*

Let G be a graph of order n and μ be an adjacency eigenvalue of G with multiplicity k ≥ 1. A star complement H for μ in G is an induced subgraph of G of order n-k with no eigenvalue μ, and the subset X = V(G-H) is called a star set for μ in G. The star complement provides a strong link between graph structure and linear algebra. In this paper, the authors characterize the regular graphs with K_2,2,s(s ≥ 2) as a star complement for all possible eigenvalues, the maximal graphs with K     

On the Hosoya index of graphs

Let G be a (molecular) graph. The Hosoya index Z(G) of G is defined as the number of subsets of the edge set E(G) in which no two edges are adjacent in G, i.e., Z(G) is the total number of matchings of G. In this paper, we determine all the connected graphs G with n + 1 ≤ Z(G) ≤ 5n ? 17 for n ≥ 19. As a byproduct, the graphs of n vertices with Hosoya index from the second smallest value to the twenty first smallest value are obtained for n ≥ 19.     

推出-拉回图上的覆盖性同态

In a pushout-pullback diagram,which consists of four morphisms f : A → B,g : A → C,α : C → D and β : B → D,we give some relations among the covers of these four modules.If kerf ∈ I(L ),then g : A → C is L -covering if and only if β : B → D is L -covering.If every module has an L -precover and kerf ∈ I(L ),then A and C have isomorphic L -precovers if and only if B and D have isomorphic L -precovers.     

给定围长的三圈图的无符号拉普拉斯谱半径

A tricyclic graph G =（V（G）, E（G）） is a connected and simple graph such that｜E（G）｜ = ｜V（G）｜＋2. Let Tg nbe the set of all tricyclic graphs on n vertices with girth g. In this paper, we will show that there exists the unique graph which has the largest signless Laplacian spectral radius among all tricyclic graphs with girth g containing exactly three（resp., four）cycles. And at the same time, we also give an upper bound of the signless Laplacian spectral radius and the extremal graph having the largest signless Laplacian spectral radius in Tg n,where g is even.     

左三角范畴的稳定化和幂等完备

Let (CΩ△) be a left triangulated category with a fully faithful endofunctor.We show a triangle-equivalence (S(C),△) ～=(S(C),△),where (S(C)△,) denotes the stabilization of the idempotent completion of (C,△) and (S(C),△) denotes the idempotent completion of the stabilization of (C,△).     

Analytic extension of differentiable functions defined in closed sets by means of continuous linear operators

In this paper we solve the following problem posed by Schmets and Valdivia: Under which conditions does there exist an extension operator from the space of the Whitney jets on a closed set to so that the extended functions are real analytic outside ?

     

Accelerated dynamical approaches for finding the unique positive solution of K S $\mathcal {K}\mathcal {S}$ -tensor equations

Numerical Algorithms - A new class of tensors called $\mathcal {K}\mathcal {S}$ -tensors, which is a subset of non-singular $\mathcal {P}$ -tensors and generalization of ${\mathscr{H}}^{+}$...     

The essentially tame local Langlands correspondence, I

Let be a non-Archimedean local field (of characteristic or ) with finite residue field of characteristic . An irreducible smooth representation of the Weil group of is called essentially tame if its restriction to wild inertia is a sum of characters. The set of isomorphism classes of irreducible, essentially tame representations of dimension is denoted . The Langlands correspondence induces a bijection of with a certain set of irreducible supercuspidal representations of . We consider the set of isomorphism classes of certain pairs , called ``admissible', consisting of a tamely ramified field extension of degree and a quasicharacter of . There is an obvious bijection of with . Using the classification of supercuspidal representations and tame lifting, we construct directly a canonical bijection of with , generalizing and simplifying a construction of Howe (1977). Together, these maps give a canonical bijection of with . We show that one obtains the Langlands correspondence by composing the map with a permutation of of the form , where is a tamely ramified character of depending on . This answers a question of Moy (1986). We calculate the character in the case where is totally ramified of odd degree.

     

Topological Graph Polynomials in Colored Group Field Theory

In this paper, we analyze the open Feynman graphs of the Colored Group Field Theory introduced in Gurau (Colored group field theory, arXiv:0907.2582 [hep-th]). We define the boundary graph ${\mathcal{G}_{\partial}}In this paper, we analyze the open Feynman graphs of the Colored Group Field Theory introduced in Gurau (Colored group field theory, arXiv:0907.2582 [hep-th]). We define the boundary graph G_?{\mathcal{G}_{\partial}} of an open graph G{\mathcal{G}} and prove it is a cellular complex. Using this structure we generalize the topological (Bollobás–Riordan) Tutte polynomials associated to (ribbon) graphs to topological polynomials adapted to Colored Group Field Theory graphs in arbitrary dimension.     

On equalities of BLUEs for a multiple restricted partitioned linear model

For the multiple restricted partitioned linear model ${\mathscr{M}}=\{y, X_1$ $\beta_1+\cdots+X_s\beta_s\mid A_1\beta_1=b_1, \cdots, A_s\beta_s=b_s, \Sigma\}$, the relationships between the restricted partitioned linear model ${\mathscr{M}}$ and the corresponding $s$ small restricted linear models ${\mathscr{M}}_i=\{y, X_i\beta_i\mid A_i\beta_i=b_i, \Sigma\},~i=1, \cdots , s$ are studied. The necessary and sufficient conditions for the best linear unbiased estimators $(\mbox{BLUEs})$ under the full restricted model to be the sums of BLUEs under the $s$ small restricted model are derived. Some statistical properties of the \mbox{BLUEs} are also described.