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.     

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.     

Asymptotic approximation for the number of <Emphasis Type="Italic">n</Emphasis>-vertex graphs of given diameter

We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices.     

A note on the Engelking-Karłowicz theorem

We investigate the chromatic number of infinite graphs whose definition is motivated by the theorem of Engelking and Kar?owicz (in [?]). In these graphs, the vertices are subsets of an ordinal, and two subsets X and Y are connected iff for some a ∈ X ∩ Y the order-type of a ∩ X is different from that of a ∩ Y.In addition to the chromatic number x(G) of these graphs we study χ _κ (G), the κ-chromatic number, which is the least cardinal µ with a decomposition of the vertices into µ classes none of which contains a κ-complete subgraph.     

Domination Defect in Graphs: Guarding With Fewer Guards

In this paper, we introduce a new graph parameter called the domination defect of a graph. The domination number γ of a graph G is the minimum number of vertices required to dominate the vertices of G. Due to the minimality of γ, if a set of vertices of G has cardinality less than γ then there are vertices of G that are not dominated by that set. The k-domination defect of G is the minimum number of vertices which are left un-dominated by a subset of γ - k vertices of G. We study different bounds on the k-domination defect of a graph G with respect to the domination number, order, degree sequence, graph homomorphisms and the existence of efficient dominating sets. We also characterize the graphs whose domination defect is 1 and find exact values of the domination defect for some particular classes of graphs.     

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.     

On a generalization of the Hadwiger–Nelson problem

For a field F and a quadratic form Q defined on an n-dimensional vector space V over F, let QG _Q , called the quadratic graph associated to Q, be the graph with the vertex set V where vertices u,w ∈ V form an edge if and only if Q(v ? w) = 1. Quadratic graphs can be viewed as natural generalizations of the unit-distance graph featuring in the famous Hadwiger–Nelson problem. In the present paper, we will prove that for a local field F of characteristic zero, the Borel chromatic number of QG _Q is infinite if and only if Q represents zero non-trivially over F. The proof employs a recent spectral bound for the Borel chromatic number of Cayley graphs, combined with an analysis of certain oscillatory integrals over local fields. As an application, we will also answer a variant of question 525 proposed in the 22nd British Combinatorics Conference 2009 [6].     

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.     

Some Properties of the Idempotent Graph of a Ring

The idempotent graph of a ring R, denoted by I(R), is a graph whose vertices are all nontrivial idempotents of R and two distinct vertices x and y are adjacent if and only if xy = yx = 0. In this paper, we show that diam\({(I(M_n(D))) = 4}\), for all natural number \({n \geq 4}\) and diam\({(I(M_3(D))) = 5}\), where D is a division ring. We also provide some classes of rings whose idempotent graphs are connected. Moreover, the regularity, clique number and chromatic number of idempotent graphs are studied.     

Hypergraphs with Zero Chromatic Threshold

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least \(c \left( {\begin{array}{c}|V(H)|\\ r-1\end{array}}\right) \) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erd?s and Simonovits. One interesting problem, first proposed by ?uczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erd?s graphs defined earlier by the authors.     

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.     

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.     

Independent sets in graphs without subtrees with many leaves

A subtree of a graph is called inscribed if no three vertices of the subtree generate a triangle in the graph. We prove that, for fixed k, the independent set problem is solvable in polynomial time for each of the following classes of graphs: (1) graphs without subtrees with k leaves, (2) subcubic graphs without inscribed subtrees with k leaves, and (3) graphs with degree not exceeding k and lacking induced subtrees with four leaves.     

Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

Elementary Graphs with Respect to <Emphasis Type="Italic">f</Emphasis>-Parity Factors

This note concerns the f-parity subgraph problem, i.e., we are given an undirected graph G and a positive integer value function \({f : V(G) \rightarrow \mathbb{N}}\), and our goal is to find a spanning subgraph F of G with deg _F ≤ f and minimizing the number of vertices x with \({\deg_F(x) \not\equiv f(x) \, {\rm mod} \, {2}}\) . First we prove a Gallai–Edmonds type structure theorem and some other known results on the f-parity subgraph problem, using an easy reduction to the matching problem. Then we use this reduction to investigate barriers and elementary graphs with respect to f-parity factors, where an elementary graph is a graph such that the union of f-parity factors form a connected spanning subgraph.     

Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

Quotient of spectral radius, (signless) Laplacian spectral radius and clique number of graphs

In this paper, the upper and lower bounds for the quotient of spectral radius (Laplacian spectral radius, signless Laplacian spectral radius) and the clique number together with the corresponding extremal graphs in the class of connected graphs with n vertices and clique number ω(2 ≤ ω ≤ n) are determined. As a consequence of our results, two conjectures given in Aouchiche (2006) and Hansen (2010) are proved.     

On countable unions of nonmeager sets in hereditarily Lindelöf spaces

It is well known that any Vitali set on the real line ? does not possess the Baire property. The same is valid for finite unions of Vitali sets. What can be said about infinite unions of Vitali sets? Let S be a Vitali set, S _r be the image of S under the translation of ? by a rational number r and F = {S _r : r is rational}. We prove that for each non-empty proper subfamily F′ of F the union ∪F′ does not possess the Baire property. We say that a subset A of ? possesses Vitali property if there exist a non-empty open set O and a meager set M such that A ? O \ M. Then we characterize those non-empty proper subfamilies F′ of F which unions ∪F′ possess the Vitali property.     

On extensions of exceptional strongly regular graphs with eigenvalue 3

The study of distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with eigenvalue 3 was initiated by Makhnev. In particular, he reduced these graphs to graphs in which neighborhoods of vertices are exceptional graphs or pseudogeometric graphs for pG _s?3(s, t). Makhnev and Paduchikh found parameters of exceptional graphs (see the proposition). In the present paper, we study amply regular graphs in which neighborhoods of vertices are exceptional strongly regular graphs with nonprincipal eigenvalue 3 and parameters from conditions 3–6 of the Proposition.     

Interval <Emphasis Type="Italic">k</Emphasis>-Graphs and Orders

An interval k-graph is the intersection graph of a family of intervals of the real line partitioned into k classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k =?2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k >?2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder.