The Number of Labeled Outerplanar <Emphasis Type="Italic">k</Emphasis>-Cyclic Graphs

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti.     

The minimum Wiener index of unicyclic graphs with a fixed diameter

The Wiener index is the sum of distances between all pairs of distinct vertices in a connected graph, which is the oldest topological index related to molecular branching. In the article we characterize the graphs having the minimum Wiener index among all n-vertex unicyclic graphs with a fixed diameter.     

Diversity vectors of balls in graphs and estimates of the components of the vectors

The diversity vectors of balls are considered (the ith component of a vector of this kind is equal to the number of different balls of radius i) for the usual connected graphs and the properties of the components of the vectors are studied. The sharp upper and lower estimates are obtained for the number of different balls of a given radius in the n-vertex graphs (trees) and n-vertex trees (graphs with n ? 2d) of diameter d. It is shown that the estimates are precise in every graph regardless of the radius of balls. It is proven a necessary and sufficient condition is given for the existence of an n-vertex graph of diameter d with local (complete) diversity of balls.     

Enumeration of labeled outerplanar bicyclic and tricyclic graphs

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n.     

The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.     

Token Graphs

For a graph G and integer k ≥ 1, we define the token graph F _k (G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F _k (G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of F _k (G) correspond to configurations of k indistinguishable tokens placed at distinct vertices of G, where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

A Polynomial Bound for Untangling Geometric Planar Graphs

To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos (Discrete Comput. Geom. 28(4): 585–592, 2002) asked if every n-vertex geometric planar graph can be untangled while keeping at least n ^ε vertices fixed. We answer this question in the affirmative with ε=1/4. The previous best known bound was \(\Omega(\sqrt{\log n/\log\log n})\). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least \(\Omega(\sqrt{n})\) vertices fixed, while the best upper bound was \(\mathcal{O}((n\log n)^{2/3})\). We answer a question of Spillner and Wolff (http://arxiv.org/abs/0709.0170) by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than \(3(\sqrt{n}-1)\) vertices fixed.     

On the least distance eigenvalues of the second power of a graph

The k-th power of a graph G, denoted by \(G^k\), is the graph obtained from G by adding an edge between each pair of vertices with distance at most k. This paper investigates the least distance eigenvalues of the second power of a connected graph, and determine the trees and unicyclic graphs with least distance eigenvalues of the second power in \([-\,3,-\,2]\) and \((-\,\frac{3+\sqrt{5}}{2}, -\,1]\), respectively.     

An approximation algorithm for finding a <Emphasis Type="Italic">d</Emphasis>-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

An approximation algorithm is suggested for the problem of finding a d-regular spanning connected subgraph of maximum weight in a complete undirected weighted n-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity O(n ²) when d = o(n). For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm.     

<Emphasis Type="Italic">s</Emphasis>-Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex \({v \in V(G)}\) , and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C _k such that \({v \in V(C_k)}\) . Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K _1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K ₃}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp _s (G), is the least nonnegative integer m such that L ^m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0,

$vp_s(G)\le \left\{\begin{array}{l@{\quad}l}\qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$

And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.     

On the asymptotic optimality of a solution of the euclidean problem of covering a graph by <Emphasis Type="Italic">m</Emphasis> nonadjacent cycles of maximum total weight

In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space R^d by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n³). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.     

Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

On the Extremal Zagreb Indices of Graphs with Cut Edges

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M ₁- and M ₂-value are obtained, respectively, and uniquely, at K _n ^k (resp. P _n ^k ), where K _n ^k is a graph obtained by joining k independent vertices to one vertex of K _n?k and P _n ^k is a graph obtained by connecting a pendent path P _k+1 to one vertex of C _n?k.     

Spectral radius of <Emphasis Type="Italic">r</Emphasis>-uniform supertrees with perfect matchings

supertree is a connected and acyclic hypergraph. The set of r-uniform supertrees with n vertices and the set of r-uniform supertrees with perfect matchings on rk vertices are denoted by T_n and T_r,k, respectively. H. Li, J. Shao, and L. Qi [J. Comb. Optim., 2016, 32(3): 741–764] proved that the hyperstar S_n,r attains uniquely the maximum spectral radius in T_n. Focusing on the spectral radius in T_r,k, this paper will give the maximum value in T_r,k and their corresponding supertree.     

Dominant dimensions,derived equivalences and tilting modules

We show that for every ? > 0 there exist δ > 0 and n₀ ∈ ? such that every 3-uniform hypergraph on n ≥ n₀ vertices with the property that every k-vertex subset, where k ≥ δn, induces at least \(\left( {\frac{1}{2} + \varepsilon } \right)\left( {\begin{array}{*{20}c} k \\ 3 \\ \end{array} } \right)\) edges, contains K₄^? as a subgraph, where K₄^? is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erd?s and Sós. The constant 1/4 is the best possible.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Classification of amply regular graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>1</Subscript> = 6

An undirected graph with v vertices in which the degrees of all vertices are equal to k, each edge is contained in exactly λ triangles, and the intersection of the neighborhoods of any two vertices at distance 2 contains exactly µ vertices is called amply regular with parameters (v, k, λ, µ). We complete the classification of amply regular graphs with b ₁ = 6, where b ₁ = k ? λ ? 1.     

On one test for the switching separability of graphs modulo <Emphasis Type="Italic">q</Emphasis>

We consider graphs whose edges are marked by numbers (weights) from 1 to q - 1 (with zero corresponding to the absence of an edge). A graph is additive if its vertices can be marked so that, for every two nonadjacent vertices, the sum of the marks modulo q is zero, and for adjacent vertices, it equals the weight of the corresponding edge. A switching of a given graph is its sum modulo q with some additive graph on the same set of vertices. A graph on n vertices is switching separable if some of its switchings has no connected components of size greater than n - 2. We consider the following separability test: If removing any vertex from G leads to a switching separable graph then G is switching separable. We prove this test for q odd and characterize the set of exclusions for q even. Connection is established between the switching separability of a graph and the reducibility of the n-ary quasigroup constructed from the graph.