Search

In mathematical chemistry, molecular descriptors serve an important role, primarily in quantitative structure–property relationship (QSPR) and quantitative structure–activity relationship (QSAR) studies. A topological index of a molecular graph is a real number that is invariant under graph isomorphism conditions and provides information about its size, symmetry, degree of branching, and cyclicity. For any graph N, the first and second Gourava indices are defined as GO1(N)=∑u′v′∈E(N)(d(u′)+d(v′)+d(u′)d(v′)) and GO2(N)=∑u′v′∈E(N)(d(u′)+d(v′))d(u′)d(v′), respectively.The independence number of a graph N, being the cardinality of its maximal independent set, plays a vital role in reading the energies of chemical trees. In this research paper, it is shown that among the family of trees of order δ and independence number ξ, the spur tree denoted as Υδ,ξ maximizes both 1st and 2nd Gourava indices, and with these characterizations this graph is unique.

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed parameter tractable. One example are block-structured integer programs, which exhibits a (recursive) block structure: The problem decomposes into independent and efficiently solvable sub-problems, if a small number of rows or columns are deleted from the constraint matrix. Prominent examples are 2-stage stochastic integer programs, n-fold integer programs and their generalizations. Previously known algorithms for these problems were based on the augmentation framework, a variant of local search tailored to integer programming. We propose a different approach. We provide new proximity bounds, independent of the number of sub-problems, for both n-fold and 2-stage stochastic integer programming. Further, we show that the relaxation can be solved efficiently via an adaptation of a parametric search framework. We apply our techniques to n-fold and 2-stage integer programming, and integer programming with bounded primal or dual treedepth. For these cases, we obtain strongly polynomial algorithms, which are near-linear in the dimension of the problem. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable. For the second part of this thesis, the focus is shifted to a different NP-hard problem, the maximum (weight) independent set problem. We consider intersection graphs of axis-parallel rectangles or segments, both in the weighted and unweighted case. Given a set of weighted axis-parallel rectangles or segments, the task is to find a subset of pairwise non-intersecting objects with the maximum possible total weight. For weighted rectangles, the best-known polynomial-time approximation algorithm achieves an approximation factor of O(log log (n)). In the unweighted setting, constant factor approximation algorithms are known. It remains open if there are also constant factor approximation algorithms for the weighted setting. We give a parameterized approximation algorithm for finding a maximum weight independent set of axis-parallel rectangles. Given a parameter k, and e>0, the algorithm finds a set of non-overlapping rectangles with weight at least (1-e) opt(k) in 2^O(k log(k/e)) n^O(1/e) time, where opt(k) is the maximum weight of a solution of cardinality at most k. Note that, our algorithm may return a solution consisting of more than k rectangles. To complement this, we also propose a parameterized approximation algorithm for the case of axis-parallel segments. Here the algorithm finds a solution with cardinality at most k and total weight at least (1-e)opt(k) in time 2^O(k^2 log(k/e)) n^O(1). Lastly, we provide a nearly tight bound on the independence number of axis-parallel segments. More precisely, we prove that for any triangle-free intersection graph of n axis-parallel segments in the plane, the independence number of this graph is at least n/4 + c sqrt(n), for an absolute constant c. We complement this with a construction of a graph in this class, with an independence number at most n/4 + d sqrt(n) for an absolute constant d.

In 1982, Papadimitriou and Yannakakis introduced the Exact Matching (EM) problem where given an edge colored graph, with colors red and blue, and an integer k, the goal is to decide whether or not the graph contains a perfect matching with exactly k red edges. Although they conjectured it to be NP-complete, soon after it was shown to be solvable in randomized polynomial time in the seminal work of Mulmuley et al., placing it in the complexity class RP. Since then, all attempts at finding a deterministic algorithm for EM have failed, thus leaving it as one of the few natural combinatorial problems in RP but not known to be contained in P, and making it an interesting instance for testing the hypothesis RP = P. Progress has been lacking even on very restrictive classes of graphs despite the problem being quite well known as evidenced by the number of works citing it. In this paper we aim to gain more insight into EM by studying a new optimization problem we call Top-k Perfect Matching (TkPM) which we show to be polynomially equivalent to EM. By virtue of being an optimization problem, it is more natural to approximate TkPM so we provide approximation algorithms for it. Some of the approximation algorithms rely on a relaxation of EM on bipartite graphs where the output is required to be a perfect matching with a number of red edges differing from k by at most k/2, which is of independent interest and generalizes to the Exact Weight Perfect Matching (EWPM) problem. We also consider parameterized algorithms and show that TkPM can be solved in FPT time parameterized by k and the independence number of the graph. This result again relies on new tools developed for EM which are also of independent interest., Leibniz International Proceedings in Informatics (LIPIcs), 254, ISSN:1868-8969, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), ISBN:978-3-95977-266-2

In this paper the problem of maximizing vertex-degree function index H f ( G ) for trees and unicyclic graphs G of order n and independence number s is solved for strictly convex functions f ( x ) . In the case of unicyclic graphs f ( x ) must also satisfy strict inequality f ( 4 ) + 3 f ( 2 ) > 3 f ( 3 ) + f ( 1 ) . These conditions are fulfilled by general first Zagreb index 0 R α ( G ) for α > 2 , second multiplicative Zagreb index ∏ 2 ( G ) and sum lordeg index S L ( G ) . The extremal graphs are unique and they are stars or have diameter equal to three or to four. The same results are valid for the corresponding minimization problem when f ( x ) is strictly concave and the inequality is reversed.

Let G be a graph and I be an interval. In this paper, we present bounds for the number m G I of Laplacian eigenvalues in I in terms of structural parameters of G. In particular, we show that m G ( n − α ( G ) , n ] ≤ n − α ( G ) and m G ( n − d ( G ) + 3 , n ] ≤ n − d ( G ) − 1 , where α ( G ) and d ( G ) denote the independence number and the diameter of G, respectively. Also, we characterize bipartite graphs that satisfy m G [ 0 , 1 ) = α ( G ) . Further, in the case of triangle-free or quadrangle-free, we prove that m G ( n − 1 , n ] ≤ 1 .

Let D be a digraph and let α ( D ) , α ′ ( D ) and λ ( D ) be independence number, the matching number and the arc-strong connectivity of D , respectively. Bang-Jensen and Thommasse in 2011 conjectured that every digraph D with λ ( D ) ≥ α ( D ) is supereulerian. In [J. Graph Theory, 81(4), (2016) 393-402], it is shown that every digraph D with λ ( D ) ≥ α ′ ( D ) is supereulerian. In this paper, we introduced the symmetric core of a digraph and use it to show that each of the following holds for a strong digraph D on n ≥ 3 vertices with λ ( D ) ≥ α ′ ( D ) − 1 . ( i ) There exists a family D ( n ) of well-characterized digraphs such that for any digraph D with α ′ ( D ) ≤ 2 , D has a spanning trial if and only if D is not a member in D ( n ) . ( i i ) If α ′ ( D ) ≥ 3 , then D has a spanning trail. ( i i i ) If α ′ ( D ) ≥ 3 and n ≥ 2 α ′ ( D ) + 3 , then D is supereulerian. ( i v ) If λ ( D ) ≥ α ′ ( D ) ≥ 4 and n ≥ 2 α ′ ( D ) + 3 , then for any pair of vertices u and v of D , D contains a spanning ( u , v ) -trail.

For a finite dimensional vector space over a field the subspace sum graph of denoted by is defined to be a simple undirected graph with vertex set as the set of all non-trivial proper subspace of and, for any two distinct vertices V1 and V2 are adjacent if and only if In this paper, we establish some inter-relationship between as a graph and as a vector space by the study of genus of subspace sum graph of vector spaces. In particular, we characterize the collection of all the vector spaces for which the subspace sum graph of is either planar, toroidal or bi-toroidal. Furthermore, we determine the independence number of for a vector space of dimension at most 5.

In this note, we disprove two conjectures on no hole anti- n -labeling of graphs proposed by Guan et al. (2019), and characterize a graph G with λ n n h ( G ) = α ( G ) , where λ n n h ( G ) and α ( G ) denote the no hole anti- n -labeling number and the independence number of G , respectively.

For a positive integer k ⩾ 1, a graph G with vertex set V is said to be k-packing colorable if there exists a mapping f : V ↦ {1, 2, . . ., k} such that any two distinct vertices x and y with the same color f(x) = f(y) are at distance at least f(x) + 1. The packing chromatic number of a graph G, denoted by χρ(G), is the smallest integer k such that G is k-packing colorable.

We consider a proper coloring of a plane graph such that no face is rainbow, where a face is rainbow if any two vertices on its boundary have distinct colors. Such a coloring is said to be proper anti-rainbow. A plane quadrangulation G is a plane graph in which all faces are bounded by a cycle of length 4. In this paper, we show that the number of colors in a proper anti-rainbow coloring of a plane quadrangulation G does not exceed 3α(G)/2, where α(G) is the independence number of G. Moreover, if the minimum degree of G is 3 or if G is 3-connected, then this bound can be improved to 5α(G)/4 or 7α(G)/6+1/3, respectively. All of these bounds are tight., This is a post-peer-review, pre-copyedit version of an article published in Graphs and Combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00373-021-02350-5

Let G be a graph and k ≥ 1 be an integer. A subset S of vertices in a graph G is called a k -component independent set of G if each component of G S has order at most k . The k -component independence number, denoted by α c k G , is the maximum order of a vertex subset that induces a subgraph with maximum component order at most k . We prove that if a tree T is of order n , then α k T ≥ k / k + 1 n . The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum k -component independent set of a tree.

Funding: Ajay Kumar is supported by CSIR-UGC JRF, New Delhi, India, through Ref No.: 19/06/2016(i)EU-V/Roll No: 417267. Lavanya Selvaganesh is financially supported by SERB, India, through Grant No.: MTR/2018/000254 under the scheme MATRICS. T. Tamizh Chelvam is supported by CSIR Emeritus Scientist Scheme of Council of Scientific and Industrial Research (No.21 (1123)/20/EMR-II), Government of India. Algebraic graph theory is the study of the interplay between algebraic structures (both abstract as well as linear structures) and graph theory. Many concepts of abstract algebra have facilitated through the construction of graphs which are used as tools in computer science. Conversely, graph theory has also helped to characterize certain algebraic properties of abstract algebraic structures. In this survey, we highlight the rich interplay between the two topics viz groups and power graphs from groups. In the last decade, extensive contribution has been made towards the investigation of power graphs. Our main motive is to provide a complete survey on the connectedness of power graphs and proper power graphs, the Laplacian and adjacency spectrum of power graph, isomorphism, and automorphism of power graphs, characterization of power graphs in terms of groups. Apart from the survey of results, this paper also contains some new material such as the contents of Section 2 (which describes the interesting case of the power graph of the Mathieu group M_{11}) and subsection 6.1 (where conditions are discussed for the reduced power graph to be not connected). We conclude this paper by presenting a set of open problems and conjectures on power graphs. Publisher PDF

Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.

Adding a connected dominating set of vertices to a graph $G$ increases its number of Hadwiger $h(G)$. Based on this obvious property in [2] we introduced a new invariant $\eta(G)$ for which $\eta(G)\leq h(G)$. We continue to study its property. For a graph $G$ with independence number three without induced chordless cycles $C_7$ and with $n(G)$ vertices, $\eta(G)\geq n(G)/4$.

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by cfc(G), is defined as the minimum number of colors that are required in order to make G conflict-free connected. In this paper, we investigate the relation between the conflict-free connection number and the independence number of a graph. We firstly show that cfc(G) ≤ α(G) for any connected graph G, and give an example to show that the bound is sharp. With this result, we prove that if T is a tree with $$\Delta(T)\geq\frac{\alpha(T)+2}{2}$$ , then cfc(T) = Δ(T).

Let G ( n , α ) be the class of block graphs on n vertices and prescribed independence number α. In this article we prove that the maximum spectral radius ρ ( G ) , among all graphs G ∈ G ( n , α ) , is reached at a unique graph. As a byproduct we obtain an upper for ρ ( G ) , when G ∈ G ( n , α ) .

Recently, the symmetric division deg ($ SDD $) index is proven to be a potentially useful molecular descriptor in QSAR and QSPR (quantitative structure-activity and structure-property relationships) studies. And its predictive capability is better than that of some popular topological indices, such as the famous geometric-arithmetic index and the second Zagreb index. In this work, the maximum $ SDD $ indices of trees with given matching number or domination number or independence number or number of pendant vertices or segments or diameter or radius are presented. Furthermore, the corresponding extremal trees are identified.

In this work we study the null space of bipartite graphs without cycles of length 0 modulo 4 (denoted as C 4 k -free bipartite graphs), and its relation to structural properties. We extend the Null Decomposition of trees, introduced by Jaume and Molina (2018), to C 4 k -free bipartite graphs. This decomposition uses the null space of the adjacency matrix of a graph G to decompose it into two different types of graphs: C N ( G ) and C S ( G ) . C N has perfect matching number. C S ( G ) has a unique maximum independent set. We obtain formulas for the independence number and the matching number of a C 4 k -free bipartite graph using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a C 4 k -free bipartite graph are related to its null decomposition.

A k -ended tree is a tree with at most k leaves. In this note, we give a simple proof for the following theorem. Let G be a connected graph and k be an integer ( k ≥ 2 ). Let S be a vertex subset of G such that α G ( S ) ≤ k + κ G ( S ) − 1 . Then, G has a k -ended tree which covers S . Moreover, the condition is sharp.

The independence polynomial of a graph G is $$I(G;x)=\sum _{k=0}^{\alpha (G)} s_{k}\cdot x^{k}$$ , where $$s_{k}$$ and $$\alpha (G)$$ denote the number of independent sets of cardinality k and the independence number of G, respectively. We say that a cycle is a $$\tilde{3}$$ -cycle if its length is divisible by 3, otherwise a non- $$\tilde{3}$$ -cycle. Define $$\phi (G)$$ to be the decycling number of G. Engstrom proved that $$|I(G;-1)| \le 2^{\phi (G)}$$ for any graph G. In this paper, we first prove that $$|I(G;-1)|\le 2^{\beta (G)}-\beta (G)$$ for graphs with non- $$\tilde{3}$$ -cycles, where $$\beta (G)$$ is the cyclomatic number of G. Infinitely many examples show that there do exist graphs satisfying $$\beta (G)=\phi (G)$$ and containing non- $$\tilde{3}$$ -cycles. In such a case, it improves the Engstrom’s result. Furthermore, $$|I(G;-1)|\le 2^{k}$$ provided that all cycles of G are pairwise disjoint, where k is the number of $$\tilde{3}$$ -cycles of G. This provides a new perspective on estimating the independence polynomial at -1 of many special graphs. In the case G contains no vertices of degree 1, $$|I(G;-1)|\le 2^{\beta (G)}-1$$ if $$\beta (G)\ge 2$$ , and $$|I(G;-1)|\le 2^{\beta (G)-1}$$ if G contains a non- $$\tilde{3}$$ -cycle.

The power-law behavior is ubiquitous in a majority of real-world networks, and it was shown to have a strong effect on various combinatorial, structural and dynamical properties of graphs. For example, it has been shown that in real-life power-law networks, both the matching number and the domination number are relatively smaller, compared with homogeneous graphs. In this paper, we study analytically several combinatorial problems for two power-law graphs with the same number of vertices, edges and the same power exponent. For both graphs, we determine exactly or recursively their matching number, independence number, domination number, the number of maximum matchings, the number of maximum independent sets and the number of minimum dominating sets. We show that power-law behavior itself cannot characterize the combinatorial properties of a heterogenous graph. Since the combinatorial properties studied here have found wide applications in different fields, such as structural controllability of complex networks, our work offers insight in the applications of these combinatorial problems in power-law graphs.

Let D be a symmetric ( v , k , λ ) design and Γ be its incidence graph. This paper focuses on the metric dimension and metric independence number of the incidence graphs of symmetric designs, along with their fractional versions. It proves that both the fractional metric dimension and the fractional metric independence number of Γ are v k + 1 − λ , which induces the lower or upper bounds on the metric dimension and metric independence number of Γ . In particular, it determines the metric dimension number or metric independence number, and their basis, of finite projective planes, finite biplanes, and trivial symmetric designs.

The edge clique cover number ecc(G) of a graph G is size of the smallest collection of complete sub-graphs whose union covers all edges of G. Chen, Jacobson, Kezdy, Lehel, Scheinerman, and Wang conjectured in 2000 that if G is claw-free, then ecc(G) is bounded above by its order (denoted n). Recently, Javadi and Hajebi verified this conjecture for claw-free graphs with independence number at least three. We study the edge clique cover number of graphs with independence number two, which are necessarily claw-free. We give the first known proof of a linear bound in n for ecc(G) for such graphs, improving upon the bound of O (n 4/3 log 1/3 n) due to Javadi, Maleki and Omoomi. More precisely we prove that ecc(G) is at most the minimum of n + δ (G) and 2n − Ω (n log n), where δ (G) is the minimum degree of G. In the fractional version of the problem, we improve these upper bounds to 3 2 n. We also verify the conjecture for some specific subfamilies, for example when the edge packing number with respect to cliques (a lower bound for ecc(G)) equals n, and when G contains no induced subgraph isomorphic to H where H is any fixed graph of order 4.

A network is an abstract structure that consists of nodes that are connected by links. A bipartite network is a type of networks where the set of nodes can be divided into two disjoint sets in a way that each link connects a node from one partition with a node from the other partition. In this paper, we first determine the maximum $ H $-index of networks in the class of all $ n $-node connected bipartite network with matching number $ t $. We obtain that the maximum $ H $-index of a bipartite network with a given matching number is $ K_{t, n-t} $. Secondly, we characterize the network with the maximum $ H $-index in the class of all the $ n $-vertex connected bipartite network of given diameter. Based on our obtain results, we establish the unique bipartite network with maximum $ H $-index among bipartite networks with a given independence number and cover of a network.

Graphs with few distinct eigenvalues have been investigated extensively. In this paper, we focus on a related problem: characterizing graphs with some eigenvalue of large multiplicity. Specifically, the normalized Laplacian matrix of a graph is considered here. Let ρ n − 1 ( G ) and ν ( G ) be the second smallest normalized Laplacian eigenvalue and the independence number of a graph G, respectively. As the main conclusions, two families of n-vertex connected graphs with some normalized Laplacian eigenvalue of multiplicity n − 3 are determined: graphs with ρ n − 1 ( G ) = 1 and graphs with ρ n − 1 ( G ) ≠ 1 and ν ( G ) = 3 . Moreover, it is proved that these graphs are determined by their normalized Laplacian spectrum.

We study the asymptotic behavior of the independence number of a random subgraph of a certain (r, s)-distance graph. We provide upper and lower bounds for the critical edge survival probability under which a phase transition occurs, i.e., large new independent sets appear in the subgraph, which did not exist in the original graph.

The enhanced power graph Pe(G) of a group G is a graph with vertex set G and two vertices are adjacent if they belong to the same cyclic subgroup. In this paper, we consider the minimum degree, ind...

The $k$-independence number of a graph $G$ is the maximum size of a set of vertices at pairwise distance greater than $k$. In this paper, for each positive integer $k$, we prove sharp upper bounds for the $k$-independence number in an $n$-vertex connected graph with given minimum and maximum degree., Comment: 16 pages, 11 figures

We obtain new upper and lower bounds for the independence number and the chromatic number of generalized preferential attachment graphs.

In the Exact Matching Problem (EM), we are given a graph equipped with a fixed coloring of its edges with two colors (red and blue), as well as a positive integer k. The task is then to decide whether the given graph contains a perfect matching exactly k of whose edges have color red. EM generalizes several important algorithmic problems such as perfect matching and restricted minimum weight spanning tree problems. When introducing the problem in 1982, Papadimitriou and Yannakakis conjectured EM to be NP-complete. Later however, Mulmuley et al. presented a randomized polynomial time algorithm for EM, which puts EM in RP. Given that to decide whether or not RP=P represents a big open challenge in complexity theory, this makes it unlikely for EM to be NP-complete, and in fact indicates the possibility of a deterministic polynomial time algorithm. EM remains one of the few natural combinatorial problems in RP which are not known to be contained in P, making it an interesting instance for testing the hypothesis RP=P. Despite EM being quite well-known, attempts to devise deterministic polynomial algorithms have remained illusive during the last 40 years and progress has been lacking even for very restrictive classes of input graphs. In this paper we push the frontier of positive results forward by proving that EM can be solved in deterministic polynomial time for input graphs of bounded independence number, and for bipartite input graphs of bounded bipartite independence number. This generalizes previous positive results for complete (bipartite) graphs which were the only known results for EM on dense graphs., Leibniz International Proceedings in Informatics (LIPIcs), 241, ISSN:1868-8969, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), ISBN:978-3-95977-256-3

For k≥1, the k-independence number αk of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α(=α1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for αk, showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials. The research of Aida Abiad is partially supported by the FWO, Belgium grant 1285921N. The research of Cristina Dalfó and Miquel Àngel Fiol has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00.

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

We obtain lower and upper bounds on general multiplicative Zagreb indices for trees with given independence number and order. Bounds on basic multiplicative Zagreb indices follow from our results. ...

The power graph $${\mathcal {P}}_{G}$$ of a finite group G is the graph whose vertex set is G, two distinct vertices are adjacent if one is a power of the other. The order supergraph $${\mathcal {S}}_{G}$$ of $${\mathcal {P}}_G$$ is the graph with vertex set G, and two distinct vertices x, y are adjacent if o(x)|o(y) or o(y)|o(x). In this paper, we study the independence number of $${\mathcal {S}}_{G}$$ and answer a question was posed by Hamzeh and Ashrafi.

A simple graph G is called $$\varDelta$$ -critical if $$\chi '(G) =\varDelta (G) +1$$ and $$\chi '(H) \le \varDelta (G)$$ for every proper subgraph H of G, where $$\varDelta (G)$$ and $$\chi '(G)$$ are the maximum degree and the chromatic index of G, respectively. Vizing in 1965 conjectured that any $$\varDelta$$ -critical graph contains a 2-factor, which is commonly referred to as Vizing’s 2-factor conjecture; In 1968, he proposed a weaker conjecture that the independence number of any $$\varDelta$$ -critical graph with order n is at most n/2, which is commonly referred to as Vizing’s independence number conjecture. Based on a construction of $$\varDelta$$ -critical graphs which is called Meredith extension first given by Meredith, we show that if $$\alpha (G')\le (\frac{1}{2}+f(\varDelta ))|V(G')|$$ for every $$\varDelta$$ -critical graph $$G'$$ with $$\delta (G')=\varDelta -1,$$ then $$\alpha (G)

Given $s \ge k\ge 3$, let $h^{(k)}(s)$ be the minimum $t$ such that there exist arbitrarily large $k$-uniform hypergraphs $H$ whose independence number is at most polylogarithmic in the number of vertices and in which every $s$ vertices span at most $t$ edges. Erd\H os and Hajnal conjectured (1972) that $h^{(k)}(s)$ can be calculated precisely using a recursive formula and Erd\H os offered \$500 for a proof of this. For $k=3$ this has been settled for many values of $s$ including powers of three but it was not known for any $k\geq 4$ and $s\geq k+2$. Here we settle the conjecture for all $s \ge k \ge 4$. We also answer a question of Bhat and R\"odl by constructing, for each $k \ge 4$, a quasirandom sequence of $k$-uniform hypergraphs with positive density and upper density at most $k!/(k^k-k)$. This result is sharp., Comment: 27 pages

A graph on $n$ vertices is called pancyclic if it contains a cycle of every length $3\le l \le n$. Given a Hamiltonian graph $G$ with independence number at most $k$ we are looking for the minimum number of vertices $f(k)$ that guarantees that $G$ is pancyclic. The problem of finding $f(k)$ was raised by Erd\H{o}s in 1972 who showed that $f(k)\le 4k^4$, and conjectured that $f(k)=\Theta(k^2)$. Improving on a result of Lee and Sudakov we show that $f(k)=O(k^{11/5})$., Comment: 12 pages, 3 figures

The independence number of circulant triangle-free graphs for 2-regular, 3-regular graphs are investigated. It is shown that the independence ratio of circulant triangle-free graphs for 3-regular graphs is at least 3/8. Some bounds for the number of vertices of r-regular circulant triangle-free graphs with independence number equal to r for odd degrees are determined. These bounds are close to Sidorenko’s bounds for even degrees.

Let G = ( V , E ) be a graph and let k be a positive integer. Let P k ( V ) = { S : S ⊆ V and | S | = k } . The k -token graph F k ( G ) is the graph with vertex set P k ( V ) and two vertices A and B are adjacent if A Δ B = { a , b } and a b ∈ E ( G ) , where Δ denotes the symmetric difference. In this paper we present several basic results on 2-token graphs.

Combinatorial problems are a fundamental research subject of theoretical computer science, and for a general graph many combinatorial problems are NP-hard and even #P-complete. Thus, it is interesting to seek or design special graphs for which these difficult combinatorial problems can be exactly solved. In this paper, we study some combinatorial problems for the Farey graphs, which are translated from Farey sequences and have received considerable attention from the scientific community. We determine exactly the domination number, the independence number, and the matching number. Moreover, we derive exact or recursive solutions to the number of minimum dominating sets, the number of dominating sets, the number of maximum independent sets, the number of independent sets, the number of maximum matchings, as well as the number of matchings. Finally, we obtain explicit expressions for the number of acyclic orientations and the number of root-connected acyclic orientations. Since the considered combinatorial problems have found wide applications in diverse fields, such as network science and graph data miming, this work is helpful for deepening our understanding of the applications for these combinatorial problems.

The distance spectral radius of a connected hypergraph is the largest eigenvalue of its distance matrix. In this paper, we obtain the k-uniform hypertree with minimum distance spectral radius among...

The independence number, coloring number and related parameters are investigated in the setting of oriented hypergraphs using the spectrum of the normalized Laplace operator. For the independence number, both an inertia--like bound and a ratio--like bound are shown. A Sandwich Theorem involving the clique number, the vector chromatic number and the coloring number is proved, as well as a lower bound for the vector chromatic number in terms of the smallest and the largest eigenvalue of the normalized Laplacian. In addition, spectral partition numbers are studied in relation to the coloring number., Comment: Linear Algebra and Its Applications, To appear

Let G=(V,E) be a graph, and let β∈R. Motivated by a service coverage maximization problem with limited resources, we study the β-differential of G. The β-differential of G, denoted by ∂β(G), is defined as ∂β(G):=max{|B(S)|−β|S|suchthatS⊆V}. The case in which β=1 is known as the differential of G, and hence ∂β(G) can be considered as a generalization of the differential ∂(G) of G. In this paper, upper and lower bounds for ∂β(G) are given in terms of its order |G|, minimum degree δ(G), maximum degree Δ(G), among other invariants of G. Likewise, the β-differential for graphs with heavy vertices is studied, extending the set of applications that this concept can have.

In any graph $G$, the domination number $\gamma(G)$ is at most the independence number $\alpha(G)$. The Inverse Domination Conjecture says that, in any isolate-free $G$, there exists pair of vertex-disjoint dominating sets $D, D'$ with $|D|=\gamma(G)$ and $|D'| \leq \alpha(G)$. Here we prove that this statement is true if the upper bound $\alpha(G)$ is replaced by $\frac{3}{2}\alpha(G) - 1$ (and $G$ is not a clique). We also prove that the conjecture holds whenever $\gamma(G)\leq 5$ or $|V(G)|\leq 16$., Comment: 9 pages

In this article, we compute vertex covering number and independence number of zero-divisor graph of idealization ring Γ(R(+)M) and we classify when the zero-divisor graph of idealization ring Γ(Z N (+)Z M ) is Eulerian graph.