Search

In this paper we introduce the notion of congruence for regions in lattice path models. This turns out to be useful for deriving a path counting formula for the auxiliary lattice path model in the presence of long steps, source and target points of which are situated near the filter restrictions. This problem was motivated by the fact, that weighted numbers of paths in such model mimic multiplicities in tensor power decomposition of Uq(sl2)-module T(1)⊗N at roots of unity. We expand on combinatorial properties of such model and introduce the punchline of a proof for explicit path counting formula. [ABSTRACT FROM AUTHOR]

In 1966 Gallai asked the following question: Do all longest paths (cycles) of a connected graph contain a common vertex? After a positive answer to Gallai's question, another question has been raised, Is there any family of graphs without Gallai's property? Menke found one such family, the square lattices. Embedding methods hold the promise to transform not just the way calculations are performed, but to significantly reduce computational costs and often used in quantum mechanics and material sciences. In this paper, we prove the existence of graphs with the empty intersection of their longest cycles as subgraphs of Archimedean lattices. [ABSTRACT FROM AUTHOR]

The odd-ballooning of a graph F is the graph obtained from F by replacing each edge in F by an odd cycle of length between 3 and q (q ≥ 3) where the new vertices of the odd cycles are all different. Given a forbidden graph H and a positive integer n, the extremal number, ex(n, H), is the maximum number of edges in a graph on n vertices that does not contain H as a subgraph. Erdös et al. and Hou et al. determined the extremal number of odd-ballooning of stars. Liu and Glebov determined the extremal number of odd-ballooning of paths and cycles respectively when replacing each edge of the paths or the cycles by a triangle. In this paper we determine the extremal number and find the extremal graphs for odd-ballooning of paths and cycles, when replacing each edge of the paths or the cycles by an odd cycle of length between 3 and q (q ≥ 3) and n is sufficiently large. [ABSTRACT FROM AUTHOR]

An edge e of a graph G is called singular if it is not on a triangle; otherwise, e is nonsingular. A vertex is called singular if it is adjacent to a singular edge; otherwise, it is called nonsingular. We prove the following. Let G be a connected claw-free graph such that every locally disconnected vertex x ∈ V(G) satisfies the following conditions: (i) if x is nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 4 nonsingular edges, (ii) if x is not nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 3 nonsingular edges, (iii) if x is of degree 2, then x is singular and x is on an induced cycle C of length at least 4 with at most 2 nonsingular edges such that G [ V (C) ∩ V 2 (G) ] is a path or a cycle. Then G is either hamiltonian, or G is the line graph of the graph obtained from K 2 , 3 by attaching a pendant edge to its each vertex of degree two. Some results on forbidden subgraph conditions for hamiltonicity in 3-connected claw-free graphs are also obtained as immediate corollaries [ABSTRACT FROM AUTHOR]

Coloring the vertices of a particular graph has often been motivated by its utility to various applied fields and its mathematical interest. A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. A dynamic k-coloring is also called a conditional (k, 2)-coloring. The smallest integer k such that G has a dynamic k-coloring is called the dynamic chromatic number χ d (G) of G. In this paper, we investigate the dynamic chromatic number for the line graph of sunlet graph and middle graph, total graph and central graph of sunlet graphs, paths and cycles. Also, we find the dynamic chromatic number for Mycielskian of paths and cycles and the join graph of paths and cycles. [ABSTRACT FROM AUTHOR]

In this paper, we present a lower bound for the domination number of the Cartesian product of a path and a cycle that is tight if the length of the cycle is a multiple of five. This bound improves the natural lower bound obtained by using the domination number of the Cartesian product of two paths that is the best one known so far. [ABSTRACT FROM AUTHOR]

A proper edge coloring is called acyclic if no bichromatic cycles are produced. It was conjectured that every simple graph G with maximum degree Δ is acyclically edge-(Δ+2)-colorable. Basavaraju and Chandran (J Graph Theory 61:192-209, 2009) confirmed the conjecture for non-regular graphs G with Δ=4. In this paper, we extend this result by showing that every 4-regular graph G without 3-cycles is acyclically edge-6-colorable. [ABSTRACT FROM AUTHOR]

A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A path P in a total-colored graph G is called a total-proper path if (1) any two adjacent edges of P are assigned distinct colors; (2) any two adjacent internal vertices of P are assigned distinct colors; and (3) any internal vertex of P is assigned a distinct color from its incident edges of P. The total-colored graph G is total-proper connected if any two distinct vertices of G are connected by a total-proper path. The total-proper connection number of a connected graph G, denoted by tpc(G), is the minimum number of colors that are required to make G total-proper connected. In this paper, we first characterize the graphs G on n vertices with tpc(G)=n-1. Based on this, we obtain a Nordhaus-Gaddum-type result for total-proper connection number. We prove that if G and G¯ are connected complementary graphs on n vertices, then 6≤tpc(G)+tpc(G¯)≤n+2. Examples are given to show that the lower bound is sharp for n≥4. The upper bound is reached for n≥4 if and only if G or G¯ is the tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

Roughly speaking, the Weyl law describes the asymptotic distribution of eigenvalues of the Laplacian that can be attached to different objects and can be analyzed in different settings. The form of the remainder term in the Weyl law is very significant in applications, and a power-saving exponent in the remainder term is appreciated. We are dealing with Laplacian defined on compact metric graph with general self-adjoint boundary conditions. The main purpose of this paper is to present application of the special form of the Tauberian theorem for the Laplace transform to the suitably transformed trace formula in the above-mentioned quantum graphs setting. The key feature of our method is that it produces a power-saving form of the reminder term and hence represents improvement in classical methods, which may be applied in other settings as well. The obtained form of the Weyl law is with the power saving of 1 / 3 in the remainder term. [ABSTRACT FROM AUTHOR]

For a graph G=(V(G),E(G)), let d(u), d(v) be the degrees of the vertices u, v in G. The first and second Zagreb indices of G are defined as M1(G)=∑u∈V(G)d(u)2 and M2(G)=∑uv∈E(G)d(u)d(v), respectively. The first (generalized) and second Multiplicative Zagreb indices of G are defined as Π1,c(G)=∏v∈V(G)d(v)c and Π2(G)=Πuv∈E(G)d(u)d(v), respectively. The (Multiplicative) Zagreb indices have been the focus of considerable research in computational chemistry dating back to Narumi and Katayama in 1980s. Denote by Gn the set of all Eulerian graphs of order n. In this paper, we characterize Eulerian graphs with first three smallest and largest Zagreb indices and Multiplicative Zagreb indices in Gn. [ABSTRACT FROM AUTHOR]

The subdivision graph S(G) of a graph G is the graph obtained by inserting a new vertex into every edge of G. Let G1 and G2 be two vertex disjoint graphs. The subdivision-vertex join of G1 and G2, denoted by G1∨˙G2, is the graph obtained from S(G1) and G2 by joining every vertex of V(G1) with every vertex of V(G2). The subdivision-edge join of G1 and G2, denoted by G1∨̲G2, is the graph obtained from S(G1) and G2 by joining every vertex of I(G1) with every vertex of V(G2), where I(G1) is the set of inserted vertices of S(G1). In this paper, we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of G1∨˙G2 (respectively, G1∨̲G2) for a regular graph G1 and an arbitrary graph G2, in terms of the corresponding spectra of G1 and G2. As applications, these results enable us to construct infinitely many pairs of cospectral graphs. We also give the number of the spanning trees and the Kirchhoff index of G1∨˙G2 (respectively, G1∨̲G2) for a regular graph G1 and an arbitrary graph G2. [ABSTRACT FROM AUTHOR]

The Wiener polarity index of a graph is defined as the number of unordered pairs of vertices at distance three. In recent years, this topological index was extensively studied since it has many known applications in chemistry and also in network theory. In this paper, we generalize the result of Behmaram et al. (Appl. Math. Lett. 25:1510-1513, 2012) for calculating the Wiener polarity index of a graph. An important advantage of our generalization is that it can be used for graphs that contain 4-cycles and also for graphs whose different cycles have more than one common edge. In addition, using the main result a closed formula for the Wiener polarity index is derived for phenylenes and recalculated for catacondensed benzenoid graphs. The catacondensed benzenoid graphs and phenylenes attaining the extremal values with respect to the Wiener polarity index are also characterized. [ABSTRACT FROM AUTHOR]

The forcing number of a perfect matching M of a graph G is the minimal number of edges of M that are contained in no other perfect matchings of G. The anti-forcing number of M in G is the minimal number of edges of G not in M whose deletion results in a subgraph with a unique perfect matching M. Recently the forcing and anti-forcing polynomials of perfect matchings of a graph were proposed as counting polynomials for perfect matchings with the same forcing number and anti-forcing number respectively. In this paper, we focus on 2×n and 3×2n grids, and obtain the explicit expressions of their forcing and anti-forcing polynomials. As corollaries, their forcing and anti-forcing spectra are obtained. [ABSTRACT FROM AUTHOR]

To overcome the difficulty in detecting reliable overlapping communities in complex networks, “true-link” and “pseudo-link” are firstly proposed on the basis of the original network graph. Then, the “true-link” graph is obtained through the preprocessing of the original network graph. And then the line graph is partitioned by means of signaling process and single-linkage hierarchical clustering. Meanwhile, the subcommunities are merged based on the proposed similarity between communities, which eradicates the inherently redundant overlapping communities to a certain extent. Compared with other overlapping community detection algorithms, this proposed algorithm is of strong robustness and high accuracy. All the results of the experiments boil down to the conclusion that this True-link Clustering Community Detection is an overlapping community detection algorithm prevailing over others. [ABSTRACT FROM AUTHOR]

We consider colorings of the pairs of a family F⊆FIN of topological type ωωk, for k>1; and we find a homogeneous family G⊆F for each coloring. As a consequence, we complete our study of the partition relation ∀l>1,α→(topω2+1)l,m2 identifying ωωω as the smallest ordinal space α<ω1 satisfying ∀l>1,α→(topω2+1)l,42. [ABSTRACT FROM AUTHOR]

In the recent years, the use of mobile sink has drawn enormous attention for data collection in wireless sensor networks (WSNs). Mobile sink is well known for solving hotspot or sinkhole problem. However, the design of an efficient path for mobile sink has tremendous impact on network lifetime and coverage in data collection process of WSNs. This is particularly an important issue for many critical applications of WSNs where data collection requires to be carried out in delay bound manner. In this paper, we propose a novel scheme for delay efficient trajectory design of a mobile sink in a cluster based WSN so that it can be used for critical applications without compromising the complete coverage of the target area. Given a set of gateways (cluster heads), our scheme determines a set of rendezvous points for designing path of the mobile sink for critical applications. The scheme is based on the Voronoi diagram. We also propose an efficient method for recovery of the orphan sensor nodes generated due to the failure of one or more cluster heads during data collection. We perform extensive simulations over the proposed algorithm and compare its results with existing algorithms to demonstrate the efficiency of the proposed algorithm in terms of network lifetime, path length, average waiting time, fault tolerance and adaptability etc. For the fault tolerance, we simulate the schemes using Weibull distribution and analyze their performances. [ABSTRACT FROM AUTHOR]

We present a new graph-based approach to the following basic problem in phylogenetic tree construction. Let P={T1,…,Tk} be a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility problem asks whether there is a phylogenetic tree T with the following property: for each i∈{1,⋯,k}, Ti can be obtained from the restriction of T to the species set of Ti by contracting zero or more edges. If such a tree T exists, we say that P is compatible and that T displays P. Our approach leads to a O(MPlog2MP) algorithm for the tree compatibility problem, where MP is the total number of nodes and edges in P. Our algorithm either returns a tree that displays P or reports that P is incompatible. Unlike previous algorithms, the running time of our method does not depend on the degrees of the nodes in the input trees. Thus, our algorithm is equally fast on highly resolved and highly unresolved trees. [ABSTRACT FROM AUTHOR]

Björklund and Husfeldt developed a randomized polynomial time algorithm to solve the shortest two disjoint paths problem. Their algorithm is based on computation of permanents modulo 4 and the isolation lemma. In this paper, we consider the following generalization of the shortest two disjoint paths problem, and develop a similar algebraic algorithm. The shortest perfect (A+B)-path packing problem is: given an undirected graph G and two disjoint node subsets A, B with even cardinalities, find shortest |A|/2+|B|/2 disjoint paths whose ends are both in A or both in B. Besides its NP-hardness, we prove that this problem can be solved in randomized polynomial time if |A|+|B| is fixed. Our algorithm basically follows the framework of Björklund and Husfeldt but uses a new technique: computation of hafnian modulo 2k combined with Gallai’s reduction from T-paths to matchings. We also generalize our technique for solving other path packing problems, and discuss its limitation. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the RMS distance (sum of squared distances between pairs of points) under translation between two point sets A and B, in the plane, with m=|B|≪n=|A|, in the partial-matching setup, in which each point in B is matched to a distinct point in A. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision DB,A of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is O(n2m3.5(elnm+e)m), so it is only quadratic in |A|. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. [ABSTRACT FROM AUTHOR]

An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition BX and BY. Then B is generating if there exists an independent set S such that S∪BX and S∪BY are both maximal independent sets of G. In the restricted case that a generating subgraph B is isomorphic to K1,1, the unique edge in B is called a relating edge. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. In this article we discuss the connections among these problems, provide proofs for NP-completeness for several restricted cases, and present polynomial characterizations for some other cases. [ABSTRACT FROM AUTHOR]

Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Krioukov et al. (in Phys Rev E 82(3):036106, 2010) and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs G and present new results on the expected number of k-cliques EKk and the size of the largest clique ω(G). We observe that there is a phase transition at power-law exponent β=3. More precisely, for β∈(2,3) we prove EKk=nk(3-β)/2Θ(k)-k and ω(G)=Θ(n(3-β)/2), while for β⩾3 we prove EKk=nΘ(k)-k and ω(G)=Θ(log(n)/loglogn). Furthermore, we show that for β⩾3, cliques in hyperbolic random graphs can be computed in time O(n). If the underlying geometry is known, cliques can be found with worst-case runtime O(m·n2.5) for all values of β. [ABSTRACT FROM AUTHOR]

For a graph G, a function ψ is called a bar visibility representation of G when for each vertex v∈V(G), ψ(v) is a horizontal line segment (bar) and uv∈E(G) if and only if there is an unobstructed, vertical, ε-wide line of sight between ψ(u) and ψ(v). Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation of G, additionally, puts the bar ψ(u) strictly below the bar ψ(v) for each directed edge (u, v) of G. We study a generalization of the recognition problem where a function ψ′ defined on a subset V′ of V(G) is given and the question is whether there is a bar visibility representation ψ of G with ψ(v)=ψ′(v) for every v∈V′. We show that for undirected graphs this problem, and other closely related problems, is NP-complete, but for certain cases involving directed graphs it is solvable in polynomial time. [ABSTRACT FROM AUTHOR]

Bus graphs are used for the visualization of hypergraphs, for example in VLSI design. Formally, they are specified by bipartite graphs G=(B∪V,E). The bus vertices B are realized by horizontal and vertical segments, and the connector vertices V are realized by points and connected orthogonally to the bus segments without any bend; this is called bus realization. The decision whether a bipartite graph admits a bus realization, where connections may cross, is NP-complete. In this paper we show that in contrast the question whether a planar bipartite graph admits a planar bus realization can be answered in polynomial time. First we deal with plane instances, i.e., with the case where a planar embedding is prescribed. We identify three necessary conditions on the partition B=BV∪BH of the bus vertices, here BV denotes the vertical and BH the horizontal buses. We provide a test whether a good partition, i.e., a partition obeying these conditions, exists. The test is based on the computation of a maximum matching on some auxiliary graph. Given a good partition we can construct a non-crossing realization of the bus graph on an O(n)×O(n) grid in linear time. In the second part we use SPQR-trees to solve the problem for general planar bipartite graphs. [ABSTRACT FROM AUTHOR]

A tree-child network is a phylogenetic network with the property that each non-leaf vertex is the parent of a tree vertex or a leaf. In this paper, we show that a tree-child network on taxa (leaf) set X with an outgroup and a positive real-valued weighting of its edges is essentially determined by the multi-set of all path-length distances between elements in X provided, for each reticulation, the edges directed into it have equal weight. Furthermore, we give a polynomial-time algorithm for reconstructing such a network from this inter-taxa distance information. Such constructions are of central importance in evolutionary biology where phylogenetic networks represent the ancestral history of a collection of present-day taxa. [ABSTRACT FROM AUTHOR]

Given an undirected simple graph G, a set of vertices is an r-clique transversal if it has at least one vertex from every r-clique. Such sets generalize vertex covers as a vertex cover is a 2-clique transversal. Perfect graphs are a well-studied class of graphs on which a minimum weight vertex cover can be obtained in polynomial time. Further, an r-clique transversal in a perfect graph is also a set of vertices whose deletion results in an (r-1)-colorable graph. In this work, we study the problem of finding a minimum weight r-clique transversal in a perfect graph. This problem is known to be NP-hard for r≥3 and admits a straightforward r-approximation algorithm. We describe two different r+12-approximation algorithms for the problem. Both the algorithms are based on (different) linear programming relaxations. The first algorithm employs the primal-dual method while the second uses rounding based on a threshold value. We also show that the problem is APX-hard and describe hardness results in the context of parameterized algorithms and kernelization. [ABSTRACT FROM AUTHOR]

A set S⊆V(G) is a k-distance independent set of a graph G if the distance between every two vertices of S is greater than k. The k-distance independence number αk(G) of G is the maximum cardinality over all k-distance independent sets in G. A k-distance coloring of G is a function f from V(G) onto a set of positive integers (colors) such that for any two distinct vertices u and v at distance less than or equal to k we have f(u)≠f(v). The k-distance chromatic number of a graph G is the smallest number of colors needed to have a k-distance coloring of G. The k-distance independence numbers and 2-distance chromatic numbers of Cartesian products of cycles are considered. A computer-aided method with the isomorphic rejection is used to determine the k-distance independence numbers of Cartesian products of cycles. By using these results, several lower and upper bounds on the maximal cardinality AqL(n,d) of a q-ary Lee code of length n with a minimum distance at least d are improved. It is also established that the 2-distance chromatic number of G equals |V(G)|α(G2) for G=Cm□Cn□Ck, whenever k≥3 and (m,n)∈{(3,3),(3,4),(3,5),(4,4)} or k, m and n are all multiples of seven. Moreover, it is shown that the 2-distance chromatic number of the three-dimensional square lattice is equal to seven. [ABSTRACT FROM AUTHOR]

A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying |L(x)∩L(y)|≤d for each edge xy. An L-coloring is a vertex coloring π such that π(v)∈L(v) for each vertex v and π(x)≠π(y) for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we prove that planar graphs without 4-cycles adjacent to 4--cycles are (3, 1)-choosable. This is a strengthening of a result which says that planar graphs without 4-cycles are (3, 1)-choosable. [ABSTRACT FROM AUTHOR]

A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we investigate the proper connection number of the complement of a graph G according to some constraints of G itself. Also, we characterize the graphs on n vertices that have proper connection number n-2. Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if G and G¯ are both connected, then 4≤pc(G)+pc(G¯)≤n, and the upper bound holds if and only if G or G¯ is the n-vertex tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

We present a general method for obtaining conservation laws for integrable PDE at negative regularity and exhibit its application to KdV, NLS, and mKdV. Our method works uniformly for these problems posed both on the line and on the circle. [ABSTRACT FROM AUTHOR]

Suppose that {Gn} is a sequence of finite graphs such that each Gn is the tangency graph of a sphere packing in Rd. Let ρn be a uniformly random vertex of Gn and suppose that (G,ρ) is the distributional limit of {(Gn,ρn)} in the sense of Benjamini and Schramm. Then the conformal growth exponent of (G,ρ) is at most d. In other words, there exists a unimodular “unit volume" weighting of the graph metric on (G,ρ) such that the volume growth of balls in the weighted path metric is bounded by a polynomial of degree d. This assertion generalizes to limits of graphs that can be “quasi-packed” in an Ahlfors d-regular metric measure space. It implies that, under moment conditions on the degree of the root ρ, the almost sure spectral dimension of G is at most d. This fact was known previously only for graphs packed in R2 (planar graphs), and the case d >  2 eluded approaches based on extremal length. In the process of bounding the spectral dimension, we establish that the spectral measure of (G,ρ) is dominated by a variant of the d-dimensional Weyl law. [ABSTRACT FROM AUTHOR]

In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Maxd-Clique and Maxd-Club: A d-clique in a graph G=(V,E) is a subset S⊆V of vertices such that for every pair of vertices u,v∈S, the distance between u and v is at most d in G. A d-club in a graph G=(V,E) is a subset S′⊆V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Maxd-Clique (Maxd-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Since Max 1-Clique and Max 1-Club are identical to Max Clique, the inapproximabilty for Max Clique shown by Zuckerman in 2007 is transferred to them. Namely, Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n1-ε for any ε>0 unless P=NP. Also, in 2002, Marinc˘ek and Mohar showed that it is NP-hard to approximate Maxd-Club to within a factor of n1/3-ε for any ε>0 and any fixed d≥2. In this paper, we strengthen the hardness result; we prove that, for any ε>0 and any fixed d≥2, it is NP-hard to approximate Maxd-Club to within a factor of n1/2-ε. Then, we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for any integer d≥2. By using the similar ideas, we show the O(n1/2)-approximation algorithm for Maxd-Clique for any d≥2. This is the best possible in polynomial time unless P=NP, as we can prove the Ω(n1/2-ε)-inapproximability. [ABSTRACT FROM AUTHOR]

Given a network represented by a graph G=(V,E), we consider a dynamical process of influence diffusion in G that evolves as follows: Initially only the nodes of a given S⊆V are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes S (a target set) that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known that the above optimization problem is hard to approximate within a factor of 2log1-ϵ|V|, for any ϵ>0. In this paper, we present a fast and surprisingly simple algorithm that exhibits the following features: (1) when applied to trees, cycles, or complete graphs, it always produces an optimal solution (i.e, a minimum size target set); (2) when applied to arbitrary networks, it always produces a solution of cardinality which improves on previously known upper bounds; (3) when applied to real-life networks, it always produces solutions that substantially outperform the ones obtained by previously published algorithms (for which no proof of optimality or performance guarantee is known in any class of graphs). [ABSTRACT FROM AUTHOR]

This paper is devoted to new results about the scaffolding problem, an integral problem of genome inference in bioinformatics. The problem consists in finding a collection of disjoint cycles and paths covering a particular graph called the “scaffold graph”. We examine the difficulty and the approximability of the scaffolding problem in special classes of graphs, either close to trees, or very dense. We propose negative and positive results, exploring the frontier between difficulty and tractability of computing and/or approximating a solution to the problem. Also, we explore a new direction through related problems consisting in finding a family of edges having a strong effect on solution weight. [ABSTRACT FROM AUTHOR]

Motivated by applications in network epidemiology, we consider the problem of determining whether it is possible to delete at most k edges from a given input graph (of small treewidth) so that the resulting graph avoids a set F of forbidden subgraphs; of particular interest is the problem of determining whether it is possible to delete at most k edges so that the resulting graph has no connected component of more than h vertices, as this bounds the worst-case size of an epidemic. While even this special case of the problem is NP-complete in general (even when h=3), we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the general problem in time 2O(|F|wr)n on an input graph having n vertices and whose treewidth is bounded by a fixed constant w, if each of the subgraphs we wish to avoid has at most r vertices. For the special case in which we wish only to ensure that no component has more than h vertices, we improve on this to give an algorithm running in time O((wh)2wn), which we have implemented and tested on real datasets based on cattle movements. [ABSTRACT FROM AUTHOR]

For any k≥2, deciding whether the linear arboricity, star arboricity, caterpillar arboricity, spider arboricity, track number, unit track number, and subchromatic index, respectively, of a bipartite graph are at most k are all NP-complete. [ABSTRACT FROM AUTHOR]

We investigate the structural and algorithmic properties of 2-community structures in graphs introduced recently by Olsen (Math Soc Sci 66(3):331-336, 2013). A 2-community structure is a partition of a vertex set into two parts such that for each vertex the numbers of neighbours in/outside its own part and the sizes of the parts are correlated. We show that some well studied graph classes as graphs of maximum degree 3, minimum degree at least |V|-3, trees and also others, have always a 2-community structure. Furthermore, a 2-community structure can be found in polynomial time in all these classes, even with additional request of connectivity in both parts. We introduce a concept of a weak 2-community and prove that in general graphs it is NP-complete to find a balanced weak 2-community structure with or without request for connectivity in both parts. On the other hand, we present a polynomial-time algorithm to solve the problem (without the condition for connectivity of parts) in graphs of degree at most 3. [ABSTRACT FROM AUTHOR]

Necessary maximality conditions for graph surfaces in a class of two-step sub-Lorentzian structures are obtained. The concept of a sub-Lorentzian mean curvature is introduced, and equations for maximal surfaces are deduced. [ABSTRACT FROM AUTHOR]

We present a simple transformation for the inversion number and major index statistics on the labelings of a rooted tree with n vertices in the form of a rake with k teeth. The special case k=0 provides a simple transformation for the Mahonian statistics on the set Sn of permutations of {1,2,⋯,n}. We also extend the transformation to a bijective interpretation of the fact that the major index of the equivalence classes of the labelings is equidistributed with the major index of the permutations in Sn satisfying the condition that the elements 1,2,⋯,k appear in increasing order. [ABSTRACT FROM AUTHOR]

It is one of fundamental theorems in graph theory that every even graph has a circuit decomposition. This classical result for ordinary graphs is extended in this paper for uniform bridgeless hypergraphs if the degree of every vertex is even. One of major open problems for shortest circuit cover was a conjecture proposed by Itai and Rodeh (Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 62, pp. 289-299. Springer, Berlin, 1978) that every bridgeless graph G has a circuit cover of total length at most |E|+|V|-1. This conjecture was solved by Fan (J Combin Theory Ser B 74:353-367, 1998) for ordinary graphs, and is extended in this paper for bridgeless hypergraphs. [ABSTRACT FROM AUTHOR]

Let colg(G) be the game coloring number of a given graph G. Define the game coloring number of a family of graphs H as colg(H):=max{colg(G):G∈H}. Let Pk be the family of planar graphs of girth at least k. We show that colg(P7)≤5. This result extends a result about the game coloring number by Wang and Zhang [10] (colg(P8)≤5). We also show that these bounds are sharp by constructing a graph G where G∈Pk for each k≤8 such that colg(G)=5. As a consequence, colg(Pk)=5 for k=7,8. [ABSTRACT FROM AUTHOR]

In this paper, we explore minimal k-connected non-Hamiltonian graphs. Graphs are said to be minimal in the context of some containment relation; we focus on subgraphs, induced subgraphs, minors, and induced minors. When k=2, we discuss all minimal 2-connected non-Hamiltonian graphs for each of these four relations. When k=3, we conjecture a set of minimal non-Hamiltonian graphs for the minor relation and we prove one case of this conjecture. In particular, we prove all 3-connected planar triangulations which do not contain the Herschel graph as a minor are Hamiltonian. [ABSTRACT FROM AUTHOR]

Let Z be the set of integers and Zl be the set of integers modulo l. A set L⊆T=Zl1×Zl2×⋯×Zlm is called a line if there exist a,b∈T such that L={a+tb∈T:t∈Z}. A set X⊆T is called a no-three-in-line set if |X∩L|≤2 for all the lines L in T. The maximum size of a no-three-in-line set is denoted by τT. Let m≥2 and k1,k2,…,km be positive integers such that gcd(ki,kj)=1 for all i, j with i≠j. In this paper, we will show that τZk1n×Zk2n×⋯×Zkmn≤2nm-1.We will give sufficient conditions for which the equality holds. When k1=k2=⋯=km=1 and n=pl where p is a prime and l≥1 is an integer, we will show that equality holds if and only if p=2 and l=1, i.e., τZpl×Zpl×⋯×Zpl=2pl(m-1) if and only if p=2 and l=1. [ABSTRACT FROM AUTHOR]

An edge colouring of a graph G is complete if for any distinct colours c1 and c2 one can find in G adjacent edges coloured with c1 and c2, respectively. The pseudoachromatic index of G is the maximum number of colours in a complete edge colouring of G. Let ψ(n) denote the pseudoachromatic index of Kn. In the paper we proved that if x≥2 is an integer and n∈{4x2-x,⋯,4x2+3x-3}, then ψ(n)≤2x(n-x-1). Let q be an even integer and let ma=(q+1)2-a. If there is a projective plane of order q, a complete edge colouring of Kma with (ma-a)q colours, a∈{-1,0,⋯,q2+1}, is presented. The main result states that if q≥4 is an integer power of 2, then ψ(ma)=(ma-a)q for any a∈{-1,0,⋯,1+4q+92-1}. [ABSTRACT FROM AUTHOR]

A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove Behzad-Vizing conjecture for product graphs. In particular, we obtain the tight bound for certain classes of graphs. [ABSTRACT FROM AUTHOR]

Let λKv be the complete graph on v vertices in which each pair of vertices is joined by exactly λ edges. An m-cycle system of λKv is a collection C of cycles of length m whose edges partition the edges of λKv. An m-cycle system C of λKv is said to be resolvable if the m-cycles in C can be partitioned into parallel classes R={R1,R2,…,Rλ(v-1)/2} and C is denoted by (v,m,λ)-RCS, R is called a resolution. If a (v,m,λ)-RCS has a pair of orthogonal resolutions, it is said to be doubly resolvable and is denoted by (v,m,λ)-DRCS. In this paper, applying direct constructions and recursive constructions, we show that a (v, 4, 2)-DRCS exists if and only if v≡0(mod4). [ABSTRACT FROM AUTHOR]

The Paul Erdős and András Gyárfás conjecture states that every graph of minimum degree at least 3 contains a simple cycle whose length is a power of two. In this paper, we prove that the conjecture holds for Cayley graphs on generalized quaternion groups, dihedral groups, semidihedral groups and groups of order $$p^3$$ . [ABSTRACT FROM AUTHOR]

Monroe Eskew (Tree properties on $$\omega _1$$ and $$\omega _2$$ , 2016. ) asked whether the tree property at $$\omega _2$$ implies there is no Kurepa tree (as is the case in the Mitchell model, or under PFA). We prove that the tree property at $$\omega _2$$ is consistent with the existence of $$\omega _1$$ -trees with as many branches as desired. [ABSTRACT FROM AUTHOR]

We study a version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k, of available colors. All of our results are with regard to competitive analysis. Previous attempts to identify optimal algorithms for this problem have failed, even for bipartite graphs. Thus, in this paper, we analyze even more restricted graph classes, paths and trees. For paths, we consider k=2, and for trees, we consider any k≥2. We prove that a natural greedy algorithm called FIRST-FIT is optimal among deterministic algorithms, on paths as well as trees. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. For trees, we prove that to obtain a better competitive ratio than FIRST-FIT, the algorithm would have to be both randomized and unfair (i.e., reject edges that could have been colored), and even such algorithms cannot be much better than FIRST-FIT. [ABSTRACT FROM AUTHOR]

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441-448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is $$\mathsf {NP}$$ -hard. We also prove $$\mathsf {NP}$$ -hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes. [ABSTRACT FROM AUTHOR]