非正则图的谱半径

讨论了由D.Stevanovi′c提出的给定顶点数n 和最大度?的非正则图的谱半径的上界,并给出了一些新的由?表示的谱半径的界.     

关于图的拟拉普拉斯谱半径

用代数方法给出了一个关于简单图的顶点度数与拟拉普拉斯谱半径的不等式,并给出了图的拟拉普拉斯谱半径的一个新上界.     

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…     

Singular Indefinite Sturm-Liouville Operators with a Spectral Gap

Singular Sturm-Liouville operators with the indefinite weight sgn(·) and a symmetric potential which has a positive limit at ∞ have a gap in the essential spectrum. Under an additional condition it is shown that in this gap are no eigenvalues. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Toughness of a Graph

Abstract

In this paper, general results on the toughness of a graph are considered. Firstly the link between toughness and connectivity is explored and then results linking toughness and the parameters binding number and integrity are given. Further, the toughness of product graphs is discussed including general results for the lexicographic product. The paper concludes with some observations on toughness and hamiltoni-city.     

Energy Spectral Specifications for the Graph Reconstruction

In this article we show that any set of pairwise nonisomorphic pseudorgraphs whose spectral energy is bounded is finite.     

Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph

Let G be a graph with n vertices, m edges and a vertex degree sequence (d ₁, d ₂,..., d _n ), where d ₁ ≥ d ₂ ≥ ... ≥ d _n . The spectral radius and the largest Laplacian eigenvalue are denoted by ϱ(G) and μ(G), respectively. We determine the graphs with

On the Neighbour-Distinguishing Index of a Graph

A proper edge colouring of a graph G is neighbour-distinguishing provided that it distinguishes adjacent vertices by sets of colours of their incident edges. It is proved that for any planar bipartite graph G with Δ(G)≥12 there is a neighbour-distinguishing edge colouring of G using at most Δ(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.     

On the Structure of a k-Connected Graph

For a k-connected graph G, we introduce the notion of a block and construct a block tree. This construction generalizes, for , the known constructions for blocks of a connected graph. We apply the introduced notions to describe the set of vertices of a k-connected graph G such that the graph remains k-connected after deleting these vertices. We discuss some problems related to simultaneous deleting of vertices of a k-connected graph without loss of k-connectivity. Bibliography: 5 titles.     

On the Differential Polynomial of a Graph

We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G; x) :=∑?(G)k=-nB_k(G) x~(n+k), where B_k(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G;x) and its coefficients.In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G.     

On the Zero-Divisor Graph of a Ring

Let R be a commutative ring with identity, Z(R) its set of zero-divisors, and Nil(R) its ideal of nilpotent elements. The zero-divisor graph of R is Γ(R) = Z(R)\{0}, with distinct vertices x and y adjacent if and only if xy = 0. In this article, we study Γ(R) for rings R with nonzero zero-divisors which satisfy certain divisibility conditions between elements of R or comparability conditions between ideals or prime ideals of R. These rings include chained rings, rings R whose prime ideals contained in Z(R) are linearly ordered, and rings R such that {0} ≠ Nil(R) ? zR for all z ∈ Z(R)\Nil(R).     

图的分散数

The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. All the bounds in this paper are tight. Moreover, for each integer k between one and the upper bound, there are infinitely many graphs with the decay number k.     

On the Cop Number of a Graph

The cop number c(G) of a graph G is an invariant connected with the genus and the girth. We prove that for a fixed k there is a polynomial-time algorithm which decides whether c(G) ≤ k. This settles a question of T. Andreae. Moreover, we show that every graph is topologically equivalent to a graph with c ≤ 2. Finally we consider a pursuit-evasion problem in Littlewood′s miscellany. We prove that two lions are not always sufficient to catch a man on a plane graph, provided the lions and the man have equal maximum speed. We deal both with a discrete motion (from vertex to vertex) and with a continuous motion. The discrete case is solved by showing that there are plane graphs of cop number 3 such that all the edges can be represented by straight segments of the same length.     

完全图删边子图的子刻画

In this paper, we show that some edges-deleted subgraphs of complete graph are determined by their spectrum with respect to the adjacency matrix as well as the Laplacian matrix.     

On String Graph Limits and the Structure of a Typical String Graph

We study limits of convergent sequences of string graphs, that is graphs with an intersection representation consisting of curves in the plane. We use these results to study the limiting behavior of a sequence of random string graphs. We also prove similar results for several related graph classes.     

图的Laplace谱半径的几类上界

本文得到图的Laplace谱半径的几类上界.通过选取适当的对角矩阵,我们得到了在一定程度上优于其他界的上界.     

A Spectral Gap Estimate and Applications

We consider the Schrödinger operator

$$ \text{-} \frac{d^{2}}{d x^{2}} + V {\text{on an interval}}~~[a,b]~{\text{with Dirichlet boundary conditions}},$$

where V is bounded from below and prove a lower bound on the first eigenvalue λ ₁ in terms of sublevel estimates: if w _V (y) = |{x ∈ [a, b] : V (x) ≤ y}|, then

$$\lambda_{1} \geq \frac{1}{250} \min\limits_{y > \min V}{\left( \frac{1}{w_{V}(y)^{2}} + y\right)}.$$

The result is sharp up to a universal constant if {x ∈ [a, b] : V(x) ≤ y} is an interval for the value of y solving the minimization problem. An immediate application is as follows: let \({\Omega } \subset \mathbb {R}^{2}\) be a convex domain and let \(u:{\Omega } \rightarrow \mathbb {R}\) be the first eigenfunction of the Laplacian ? Δ on Ω with Dirichlet boundary conditions on ?Ω. We prove

$$\| u \|_{L^{\infty}({\Omega})} \lesssim \frac{1}{\text{inrad}({\Omega})} \left( \frac{\text{inrad}({\Omega})}{\text{diam}({\Omega})} \right)^{1/6} \|u\|_{L^{2}({\Omega})},$$

which answers a question of van den Berg in the special case of two dimensions.

     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.