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 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.     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+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.     

2-Domination number of generalized Petersen graphs

Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) is a k-dominating set of G if each vertex in \(V-S\) is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs \(P(5k+1, 2)\) and \(P(5k+2, 2)\), for \(k>0\), is \(4k+2\) and \(4k+3\), respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and \(P(5k+4,3)\). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs \(P(5k+1, 3), P(5k+2,3)\) and \(P(5k+3, 3).\)     

Extendability of Contractible Configurations for Nowhere-Zero Flows and Modulo Orientations

Let H be a connected graph and G be a supergraph of H. It is trivial that for any k-flow (D, f) of G, the restriction of (D, f) on the edge subset E(G / H) is a k-flow of the contracted graph G / H. However, the other direction of the question is neither trivial nor straightforward at all: for any k-flow \((D',f')\) of the contracted graph G / H, whether or not the supergraph G admits a k-flow (D, f) that is consistent with \((D',f')\) in the edge subset E(G / H). In this paper, we will investigate contractible configurations and their extendability for integer flows, group flows, and modulo orientations. We show that no integer flow contractible graphs are extension consistent while some group flow contractible graphs are also extension consistent. We also show that every modulo \((2k+1)\)-orientation contractible configuration is also extension consistent and there are no modulo (2k)-orientation contractible graphs.     

The graph Kre(4) does not exist

Suppose that a strongly regular graph Γ with parameters (v, k, λ, μ) has eigenvalues k, r, and s. If the graphs Γ and \(\bar \Gamma \) are connected, then the following inequalities, known as Krein’s conditions, hold: (i) (r + 1)(k + r + 2rs) ≤ (k + r)(s + 1)² and (ii) (s + 1)(k + s + 2rs) ≤ (k + s)(r + 1)². We say that Γ is a Krein graph if one of Krein’s conditions (i) and (ii) is an equality for this graph. A triangle-free Krein graph has parameters ((r ² + 3r)², r ³ + 3r ² + r, 0, r ² + r). We denote such a graph by Kre(r). It is known that, in the cases r = 1 and r = 2, the graphs Kre(r) exist and are unique; these are the Clebsch and Higman–Sims graphs, respectively. The latter was constructed in 1968 together with the Higman–Sims sporadic simple group. A.L. Gavrilyuk and A.A. Makhnev have proved that the graph Kre(3) does not exist. In this paper, it is proved that the graph Kre(4) (a strongly regular graph with parameters (784, 116, 0, 20)) does not exist either.     

Strictly Deza line graphs

For a given graph G, its line graph L(G) is defined as the graph with vertex set equal to the edge set of G in which two vertices are adjacent if and only if the corresponding edges of G have exactly one common vertex. A k-regular graph of diameter 2 on υ vertices is called a strictly Deza graph with parameters (υ, k, b, a) if it is not strongly regular and any two vertices have a or b common neighbors. We give a classification of strictly Deza line graphs.     

Edge-colouring of graphs and hereditary graph properties

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph G, a hereditary graph property P and l ? 1 we define \(X{'_{P,l}}\)(G) to be the minimum number of colours needed to properly colour the edges of G, such that any subgraph of G induced by edges coloured by (at most) l colours is in P. We present a necessary and sufficient condition for the existence of \(X{'_{P,l}}\)(G). We focus on edge-colourings of graphs with respect to the hereditary properties O_k and S_k, where O_k contains all graphs whose components have order at most k+1, and S_k contains all graphs of maximum degree at most k. We determine the value of \(X{'_{{S_k},l}}(G)\) for any graph G, k ? 1, l ? 1, and we present a number of results on \(X{'_{{O_k},l}}(G)\).     

Sharpening an Ore-type version of the Corrádi–Hajnal theorem

Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all \(k\ge 1\) and \(n\ge 3k\), every (simple) graph G on n vertices with minimum degree \(\delta (G)\ge 2k\) contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corrádi–Hajnal theorem: For all \(k\ge 1\) and \(n\ge 3k\), every graph G on n vertices contains k disjoint cycles, provided that \(d(x)+d(y)\ge 4k-1\) for all distinct nonadjacent vertices x, y. Very recently, it was refined for \(k\ge 3\) and \(n\ge 3k+1\): If G is a graph on n vertices such that \(d(x)+d(y)\ge 4k-3\) for all distinct nonadjacent vertices x, y, then G has k vertex-disjoint cycles if and only if the independence number \(\alpha (G)\le n-2k\) and G is not one of two small exceptions in the case \(k=3\). But the most difficult case, \(n=3k\), was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings.     

<Emphasis Type="Italic">k</Emphasis>-Trails: recognition,complexity, and approximations

The notion of degree-constrained spanning hierarchies, also called k-trails, was recently introduced in the context of network routing problems. They describe graphs that are homomorphic images of connected graphs of degree at most k. First results highlight several interesting advantages of k-trails compared to previous routing approaches. However, so far, only little is known regarding computational aspects of k-trails. In this work we aim to fill this gap by presenting how k-trails can be analyzed using techniques from algorithmic matroid theory. Exploiting this connection, we resolve several open questions about k-trails. In particular, we show that one can recognize efficiently whether a graph is a k-trail, and every graph containing a k-trail is a \((k+1)\)-trail. Moreover, further leveraging the connection to matroids, we consider the problem of finding a minimum weight k-trail contained in a graph G. We show that one can efficiently find a \((2k-1)\)-trail contained in G whose weight is no more than the cheapest k-trail contained in G, even when allowing negative weights. The above results settle several open questions raised by Molnár, Newman, and Seb?.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

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.     

On strongly regular graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>1</Subscript> &lt; 24

Let γ be a connected edge-regular graph with parameters (v, k, λ), and let b ₁ = k?λ?1. It is well known that, if b ₁ = 1, then Γ is either a polygon or a complete multipartite graph with parts of order 2. Graphs with b ₁ ≤ 4 were classified earlier. The investigation of graphs even in the case b ₁ = 5 involves great difficulties. However, for strongly regular graphs, the situation is much simpler. In this paper, we classify strongly regular graphs with b ₁ < 24.     

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.     

On the automorphism group of the Aschbacher graph

A Moore graph is a regular graph of degree k and diameter d with v vertices such that v ≤ 1 + k + k(k ? 1) + ... + k(k ? 1)^d?1. It is known that a Moore graph of degree k ≥ 3 has diameter 2; i.e., it is strongly regular with parameters λ = 0, µ = 1, and v = k ² + 1, where the degree k is equal to 3, 7, or 57. It is unknown whether there exists a Moore graph of degree k = 57. Aschbacher showed that a Moore graph with k = 57 is not a graph of rank 3. In this connection, we call a Moore graph with k = 57 the Aschbacher graph and investigate its automorphism group G without additional assumptions (earlier, it was assumed that G contains an involution).     

Hamiltonian Type Properties in Claw-Free $$P_5$$-Free Graphs

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each integer r in the set \(\{ m, m + 1, \ldots , n \}\). This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree et al. in (Graphs Combin 20:291–310, 2004). The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. Broersma and Veldman showed in (Contemporary methods in graph theory, BI-Wiss.-Verlag, Mannheim, Wien, Zürich, pp 181–194, 1990) that any 2-connected claw-free \(P_5\)-free graph must be hamiltonian. In fact, every non-hamiltonian cycle in such a graph is either extendable or very dense. We show that any 2-connected claw-free \(P_5\)-free graph is (k, 3k)-pancyclic for each integer \(k \ge 2\). We also show that such a graph is (1, 5)-pancyclic. Examples are provided which show that these results are best possible. Each example we provide represents an infinite family of graphs.     

Acyclic colorings of graphs with bounded degree

A k-coloring (not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k-colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5-coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2-coloring in which each color class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic t-improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.     

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.     

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.