共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
In this paper we introduce new models of random graphs, arising from Latin squares which include random Cayley graphs as a special case. We investigate some properties of these graphs including their clique, independence and chromatic numbers, their expansion properties as well as their connectivity and Hamiltonicity. The results obtained are compared with other models of random graphs and several similarities and differences are pointed out. For many properties our results for the general case are as strong as the known results for random Cayley graphs and sometimes improve the previously best results for the Cayley case. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 相似文献
3.
A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets. 相似文献
4.
Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time. 相似文献
5.
Ekkehard Khler 《Journal of Discrete Algorithms》2004,2(4):439-452
We consider the problem of recognizing AT-free graphs. Although there is a simple O(n3) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in
,
, and O(n2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs. 相似文献
6.
In data science, data are often represented by using an undirected graph where vertices represent objects and edges describe a relationship between two objects. In many applications, there can be many relations arising from different sources and/or different types of models. Clustering of multiple undirected graphs over the same set of vertices can be studied. Existing clustering methods of multiple graphs involve costly optimization and/or tensor computation. In this paper, we study block spectral clustering methods for these multiple graphs. The main contribution of this paper is to propose and construct block Laplacian matrices for clustering of multiple graphs. We present a novel variant of the Laplacian matrix called the block intra‐normalized Laplacian and prove the conditions required for zero eigenvalues in this variant. We also show that eigenvectors of the constructed block Laplacian matrix can be shown to be solutions of the relaxation of multiple graphs cut problems, and the lower and upper bounds of the optimal solutions of multiple graphs cut problems can also be established. Experimental results are given to demonstrate that the clustering accuracy and the computational time of the proposed method are better than those of tested clustering methods for multiple graphs. 相似文献
7.
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete
graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge
of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper
we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs.
Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality.
We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof
is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities
of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing
inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
相似文献
8.
We study the low energy asymptotics of periodic and random Laplace operators on Cayley graphs of amenable, finitely generated groups. For the periodic operator the asymptotics is characterised by the van Hove exponent or zeroth Novikov–Shubin invariant. The random model we consider is given in terms of an adjacency Laplacian on site or edge percolation subgraphs of the Cayley graph. The asymptotic behaviour of the spectral distribution is exponential, characterised by the Lifshitz exponent. We show that for the adjacency Laplacian the two invariants/exponents coincide. The result holds also for more general symmetric transition operators. For combinatorial Laplacians one has a different universal behaviour of the low energy asymptotics of the spectral distribution function, which can be actually established on quasi-transitive graphs without an amenability assumption. The latter result holds also for long range bond percolation models. 相似文献
9.
The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods.In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.This is a written account of an invited lecture delivered by the second author on occasion of the 12. Symposium on Operations Research, Passau, 9.–11. 9. 1987. 相似文献
10.
We use the correspondence between hypergraphs and their associated edge ideals to study the minimal graded free resolution
of squarefree monomial ideals. The theme of this paper is to understand how the combinatorial structure of a hypergraph ℋ
appears within the resolution of its edge ideal ℐ(ℋ). We discuss when recursive formulas to compute the graded Betti numbers
of ℐ(ℋ) in terms of its sub-hypergraphs can be obtained; these results generalize our previous work (Hà, H.T., Van Tuyl, A.
in J. Algebra 309:405–425, 2007) on the edge ideals of simple graphs. We introduce a class of hypergraphs, which we call properly-connected, that naturally
generalizes simple graphs from the point of view that distances between intersecting edges are “well behaved.” For such a
hypergraph ℋ (and thus, for any simple graph), we give a lower bound for the regularity of ℐ(ℋ) via combinatorial information
describing ℋ and an upper bound for the regularity when ℋ=G is a simple graph. We also introduce triangulated hypergraphs that are properly-connected hypergraphs generalizing chordal
graphs. When ℋ is a triangulated hypergraph, we explicitly compute the regularity of ℐ(ℋ) and show that the graded Betti numbers
of ℐ(ℋ) are independent of the ground field. As a consequence, many known results about the graded Betti numbers of forests
can now be extended to chordal graphs.
Dedicated to Anthony V. Geramita on the occasion of his 65th birthday. 相似文献
11.
Motivated by a fundamental geometrical object, the cut locus, we introduce and study a new combinatorial structure on graphs. 相似文献
12.
We study the spectra of several graphs generated by Sidon sets and algebraic equations over finite fields. These graphs are used to study some combinatorial problems in finite fields, such as sum product estimates, solvability of some equations and the distribution of their solutions. 相似文献
13.
林跃峰 《数学的实践与认识》2013,43(10)
研究次极大图(即链环分支数等于基圈数的连通平图)的唯一性.证明了无割点且包含子图K_4的连通平图G是次极大图当且仅当G同构于K_4,并刻画了包含子图K_4的次极大图的结构. 相似文献
14.
Flavia Bonomo Guillermo Durán Min Chih Lin Jayme L Szwarcfiter 《Mathematical Programming》2006,105(2-3):233-250
Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs,
and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs
and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs.
Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial
time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these
subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique
graph operator.
Received: April, 2004 相似文献
15.
We give a combinatorial upper bound for the gonality of a curve that is defined by a bivariate Laurent polynomial with given
Newton polygon. We conjecture that this bound is generically attained, and provide proofs in a considerable number of special
cases. One proof technique uses recent work of M. Baker on linear systems on graphs, by means of which we reduce our conjecture
to a purely combinatorial statement. 相似文献
16.
Vasiliy A. Ustimenko 《Acta Appl Math》2002,74(2):117-153
A combinatorial method of encryption with a similarity to the classical scheme of linear coding has been suggested by the author. The general idea is to treat vertices of a graph as messages and arcs of a certain length as encryption tools. We will study the quality of such an encryption in the case of graphs of high girth by comparing the probability to guess the message, (vertex) at random with the probability of breaking the key, i.e. guessing the encoding arc. In fact, the quality is good for graphs which are close to the Erdös bound, defined by the Even Cycle Theorem.In the case of parallelotopic graphs, there is a uniform way to match arcs with strings in a certain alphabet. Among parallelotopic graphs we distinguish linguistic graphs of affine type whose vertices (messages) and arcs (encoding tools) both could be naturally identified with vectors over the GF(q), and neighbors of the vertex defined by a system of linear equations. We will discuss families of linguistic and parallelotopic graphs of increasing girth as the source for assymmetric cryptographic functions and related open key algorithms.Several constructions of families of linguistic graphs of high girth with good quality, complexity and expansion coefficients will be considered. Some of those constructions have been obtained via group-theoretical and geometrical techniques. 相似文献
17.
Stavros D. Nikolopoulos 《Discrete Applied Mathematics》2002,120(1-3):165-195
A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log2 n) time using O(n2/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree. 相似文献
18.
We prove that the total curvature of a planar graph with nonnegative combinatorial curvature is at least 1/12 if it is positive. Moreover, we classify the metric structures of ambient polygonal surfaces for planar graphs attaining this bound. 相似文献
19.
20.
《Random Structures and Algorithms》2018,53(3):537-558
We study Gibbs partitions that typically form a unique giant component. The remainder is shown to converge in total variation toward a Boltzmann‐distributed limit structure. We demonstrate how this setting encompasses arbitrary weighted assemblies of tree‐like combinatorial structures. As an application, we establish smooth growth along lattices for small block‐stable classes of graphs. Random graphs with n vertices from such classes are shown to form a giant connected component. The small fragments may converge toward different Poisson Boltzmann limit graphs, depending along which lattice we let n tend to infinity. Since proper addable minor‐closed classes of graphs belong to the more general family of small block‐stable classes, this recovers and generalizes results by McDiarmid (2009). 相似文献