关于n-可扩图的一些结果

本文讨论了关于m-可扩图的两个极值问题；并考查了下述图类的n-可扩性；正则偶图，单位区间图和分裂图。     

The Laplacian spectral radius for unicyclic graphs with given independence number

In this paper, we give a complete characterization of the extremal graphs with maximal Laplacian spectral radius among all unicyclic graphs with given order and given number of pendent vertices. Then we study the Laplacian spectral radius of unicyclic graphs with given independence number and characterize the extremal graphs completely.     

The signless Laplacian spectral radius of bicyclic graphs with prescribed degree sequences

In this paper, we characterize all extremal connected bicyclic graphs with the largest signless Laplacian spectral radius in the set of all connected bicyclic graphs with prescribed degree sequences. Moreover, the signless Laplacian majorization theorem is proved to be true for connected bicyclic graphs. As corollaries, all extremal connected bicyclic graphs having the largest signless Laplacian spectral radius are obtained in the set of all connected bicyclic graphs of order n (resp. all connected bicyclic graphs with a specified number of pendant vertices, and all connected bicyclic graphs with given maximum degree).     

Graphs with few total dominating sets

We give a lower bound for the number of total dominating sets of a graph together with a characterization of the extremal graphs, for trees as well as arbitrary connected graphs of given order. Moreover, we obtain a sharp lower bound involving both the order and the total domination number, and characterize the extremal graphs as well.     

Intersections of graphs

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H. We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K₂ with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P, the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011     

The Algebraic Connectivity of Graphs with Given Matching Number

The algebraic connectivity of a graph is the second smallest eigenvalue of the associated Laplacian matrix. In this paper, we not only characterize the extremal graphs with the maximal algebraic connectivity among all graphs of order n with given matching number, but also determine the extremal tree with the maximal algebraic connectivity among all trees of order n with given matching number.     

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.     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Majorants and minorants for the classes of graphs with fixed diameter and number of vertices

We study majorants (minorants) for the classes of n-vertex diameter d graphs, that is, the extremal graphs on which the sharp upper (lower) bounds are attained for the number of distinct radius i balls for every i ≥ 0. We explicitly describe the minorants for all values of n and d, determine when the class of n-vertex diameter d graphs contains majorants, and describe these extremal graphs.     

Laplacian and signless Laplacian spectral radii of graphs with fixed domination number

We determine the maximal Laplacian and signless Laplacian spectral radii for graphs with fixed number of vertices and domination number, and characterize the extremal graphs.     

On bags and bugs

Usual graph classes, such as complete graphs, paths, cycles and stars, frequently appear as extremal graphs in graph theory problems. Here we want to turn the reader's attention to two novel, simply defined, graph classes that appear as extremal graphs in several graph theory problems. We call them bags and bugs. As examples of problems where bags and bugs appear, we show that balanced bugs maximize the index of graphs with fixed number of vertices and diameter ?2, while odd bags maximize the index of graphs with fixed number of vertices and radius ?3.     

Further results on monotonic graph invariants and bipartiteness number

Abstract

The bipartiteness of a graph is the minimum number of vertices whose deletion from G results in a bipartite graph. If a graph invariant decreases or increases with addition of edges of its complement, then it is called a monotonic graph invariant. In this article, we determine the extremal values of some famous monotonic graph invariants, and characterize the corresponding extremal graphs in the class of all connected graphs with a given vertex bipartiteness.     

On the Reverse Wiener Indices of Unicyclic Graphs

We determine the maximum values of the reverse Wiener indices of the unicyclic graphs with given cycle length, number of pendent vertices and maximum degree, respectively, and characterize the extremal graphs. We also determine the unicyclic graphs of given cycle length and diameter with minimum Wiener index.      

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

单圈共轭图的最小广义Randic指标R-1

图G的广义Randic指标定义为Rα=Rα（G）=∑uv∈E（G）（d（u）d（v））^α,其中d（u）是G的顶点u的度,α是任意实数．本文确定了单圈共轭图的广义Randic指标R-1的严格下界,并刻划了达到最小R-1的极图,这类极图还是化学图．     

The signless Laplacian spectral radius of graphs with given degree sequences

In this paper, we investigate the properties of the largest signless Laplacian spectral radius in the set of all simple connected graphs with a given degree sequence. These results are used to characterize the unicyclic graphs that have the largest signless Laplacian spectral radius for a given unicyclic graphic degree sequence. Moreover, all extremal unicyclic graphs having the largest signless Laplacian spectral radius are obtained in the sets of all unicyclic graphs of order n with a specified number of leaves or maximum degree or independence number or matching number.     

Saturation Numbers for Nearly Complete Graphs

An upper bound on the saturation number for graphs as well as associated extremal graphs was given by (Kászonyi and Tuza in J. Graph Theory, 10:203–210, 1986). A minor improvement of that result, which was implied in their paper, will be stated. Using this result, a series of exact saturation numbers and associated extremal graphs will be proved for the nearly complete graphs K _t ? E(L), where L is a graph of order at most 4.     

On graphs determining links with maximal number of components via medial construction

Let G be a connected plane graph, D(G) be the corresponding link diagram via medial construction, and μ(D(G)) be the number of components of the link diagram D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1, where n(G) is the nullity of G. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K₁ by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs.     

Zagreb,Harary and hyper-Wiener indices of graphs with a given matching number

In this paper, we present sharp bounds for the Zagreb indices, Harary index and hyper-Wiener index of graphs with a given matching number, and we also completely determine the extremal graphs.     

Maximal independent sets in bipartite graphs

A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order n and the extremal graphs as well as the corresponding results for connected bipartite graphs. © 1993 John Wiley & Sons, Inc.