An extension of regular supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we consider an extension of regular supermagic graphs and apply it to some constructions of supermagic graphs. Using the extension we prove that for any graph G there is a supermagic regular graph which contains an induced subgraph isomorphic to G.     

Finite vertex primitive 2-arc regular graphs

A classification is given of finite graphs that are vertex primitive and 2-arc regular. The classification involves various new constructions of interesting 2-arc transitive graphs.     

图的因子和因子分解的若干进展

本文综述了图的的因子和因子分解近年来的一些新结果。主要有图的因子与各种参数之间的关系,图有某种因子的一些充分必要条件,特别是图有ｋ－因子的一些充分条件以及关于图的因子分解和正交因子分解的一些新结果。文中提出了一些新的问题和猜想。     

Block-diagonal semidefinite programming hierarchies for 0/1 programming

Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for 0/1 linear programming problems. We revisit these two constructions and propose two new, block-diagonal hierarchies, which are at least as strong as the Lovász-Schrijver hierarchy, but less costly to compute. We report experimental results for the stable set problem of Paley graphs.     

Block spectral clustering methods for multiple graphs

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.     

Two-ended regular median graphs

We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends.For cubic median graphs G the condition of linear growth can be weakened to the condition that G has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.     

Energy and NEPS of graphs

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. We study the energy of the noncomplete extended p-sum (NEPS) of the graphs, a very general composition of the graphs in which the special case is the product of graphs. We show that the energy of the product of graphs is the product of the energy of graphs, and how this result may be used to construct arbitrarily large families of noncospectral connected graphs having the same number of vertices and the same energy. Further, unlike the product, we show that the energy of any other NEPS of the graphs cannot be represented as a function of the energy of starting graphs.     

Graphs with Special Arcs and Cryptography

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.     

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of λ-precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for λ-precision unit disk graphs many more graph problems have efficient approximation schemes.Our NC-approximation schemes can also be extended to obtain efficient NC-approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natural PSPACE-hard optimization problems.     

原始图与三次图的可圈度

本文综述关于原始图与三次图的可圈度的近期结果并提出一些未解决的问题。     

Parameterized complexity of even/odd subgraph problems

We study the parameterized complexity of the problems of determining whether a graph contains a k-edge subgraph (k-vertex induced subgraph) that is a Π-graph for Π-graphs being one of the following four classes of graphs: Eulerian graphs, even graphs, odd graphs, and connected odd graphs. We also consider the parameterized complexity of their parametric dual problems.For these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan.     

Locally 2‐arc transitive graphs,homogeneous factorizations,and partial linear spaces

We establish natural bijections between three different classes of combinatorial objects; namely certain families of locally 2‐arc transitive graphs, partial linear spaces, and homogeneous factorizations of arc‐transitive graphs. Moreover, the bijections intertwine the actions of the relevant automorphism groups. Thus constructions in any of these areas provide examples for the others. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 139–148, 2006     

Uncountable families of vertex-transitive graphs of finite degree

We prove that the set of vertex-transitive graphs of finite degree is uncountably large.     

Bipolar neutrosophic planar graphs

Fuzzy graph theory is used for solving real-world problems in different fields, including theoretical computer science, engineering, physics, combinatorics and medical sciences. In this paper, we present conepts of bipolar neutrosophic multigraphs, bipolar neutrosophic planar graphs, bipolar neutrosophic dual graphs, and study some of their related properties. We also describe applications of bipolar neutrosophic graphs in road network and electrical connections.     

Gromov hyperbolicity of periodic planar graphs

The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it.The main result in this paper is a very simple characterization of the hyperbolicity of a large class of periodic planar graphs.     

图的局部k限制边连通性及最优性

首先研究图的局部k限制边连通性问题和局部λ_k-连通图的存在性问题.然后研究图的局部λ_k最优性,并且应用邻域条件得到了一个保证图局部λ_k最优的充分条件.     

Some Elementary Ramanujan Graphs

We give elementary constructions of two infinite families of Ramanujan graphs of unbounded degree. The first uses the geometry of buildings over finite fields, and the second uses triangulations of modular curves.Mathematics Subject Classiffications (2000). Primary: 05C25; secondary: 05C50, 51E24     

Graph theoretic approach to parallel gene assembly

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.     

两类广义控制问题的NP-完全性

研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题, 证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的. 作为上述结果的推论, 给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明, 并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.     

Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey

A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs.