关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G1,G2,且|G1 |≥2,|G2 |≥2,则称T是G的一个非平凡点割.假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图.证明了对任意一个k≥5且t＞k/2的整数,若G是一个不含(K2+tK1)的k-连通图,且G中任...     

Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs

Bollob′as and Gy′arf′as conjectured that for n4(k-1) every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n-2k+2 verticesLiu, et alproved that the conjecture holds when n≥13k-15In this note, we characterize all the2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n-2k+2 vertices for n≥13k-15.     

Removable edges in a spanning tree of a k-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.     

On k-critical 2k-connected graphs

A graph G is called an (n, k)-graph if k(G - S) = n - |S| for any S V(G) with |S| ≤ k, where k.(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K2k+2 - (1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3, 4. We prove the conjecture for the general case k ≥ 5.     

A result on combinatorial curvature for embedded graphs on a surface

Let G be an infinite graph embedded in a surface such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, we define the combinatorial curvature

     

Quasi‐random graphs with given degree sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z _n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Hamiltonicity of 4-connected graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

A note on vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions

We show that the result of Watkins (1990) [19] on constructing vertex-transitive non-Cayley graphs from line graphs yields a simple method that produces infinite families of vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions. We also prove that the graphs arising this way are hamiltonian provided that their valency is at least six.     

强拟\alpha-预不变凸函数

研究了一类重要的广凸函数------强拟$\alpha$-预不变凸函数,讨论了它与拟\,$\alpha$-预不变凸函数、严格拟\,$\alpha$-预不变凸函数及半严格拟\,$\alpha$-预不变凸函数之间的关系,并在中间点的强拟\,$\alpha$-预不变凸性下得到了它的三个重要的性质定理,同时给出了强拟\,$\alpha$-预不变凸函 数在数学规划中的两个重要应用,这些结果在一定程度上完善了对强拟\,$\alpha$-预不变凸函数的研究.     

Hamiltonian s-properties and eigenvalues of k-connected graphs

Chvátal and Erdös (1972) [5] proved that, for a k-connected graph G, if the stability number $\alpha (G)\le k?s$, then G is Hamilton-connected ($s=1$) or Hamiltonian ($s=0$) or traceable ($s=?1$). Motivated by the result, we focus on tight sufficient spectral conditions for k-connected graphs to possess Hamiltonian s-properties. We say that a graph possesses Hamiltonian s-properties, which means that the graph is Hamilton-connected if $s=1$, Hamiltonian if $s=0$, and traceable if $s=?1$.For a real number $a\ge 0$, and for a k-connected graph G with order n, degree diagonal matrix $D(G)$ and adjacency matrix $A(G)$, we have identified best possible upper bounds for the spectral radius ${\lambda }_1(aD(\mathrm{\Gamma })+A(\mathrm{\Gamma }))$, where Γ is either G or the complement of G, to warrant that G possesses Hamiltonian s-properties. Sufficient conditions for a graph G to possess Hamiltonian s-properties in terms of upper bounds for the Laplacian spectral radius as well as lower bounds of the algebraic connectivity of G are also obtained. Other best possible spectral conditions for Hamiltonian s-properties are also discussed.     

On the maximum number of copies of H in graphs with given size and order

We study the maximum number $ex\left(n,e,H\right)$ of copies of a graph $H$ in graphs with a given number of vertices and edges. We show that for any fixed graph $H,ex\left(n,e,H\right)$ is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.     

A note on degree-continuous graphs

The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.     

A new result about panconnectivity on graphs

LetG be a simple graph such that the sum of the degrees of any two independent vertices ofG is at leastn–1. We shall prove thatG is [6,n]-panconnected except for four kinds of graphs.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

A counterexample on contractible transformations on graphs

Ivashchenko proposed the study of contractible transformations on graphs because of their applications to computer image analysis, theory of molecular spaces, and digital topology. He published five papers on this subject. Contractible transformations have recently been applied to topological data analysis. This paper presents a counterexample to several results that appeared in one of Ivashchenko’s works.     

A characterization of cycle-forced bipartite graphs

A forced cycle$C$ of a graph $G$ is a cycle in $G$ such that $G?V\left(C\right)$ has a unique perfect matching. A graph $G$ is a cycle-forced graph if every cycle in $G$ is a forced cycle. In this paper, we give a characterization of cycle-forced hamiltonian bipartite graphs.