Search

For a connected graph G , the eccentric connectivity index (ECI) and connective eccentricity index (CEI) of G are, respectively, defined as ξ c ( G ) = ∑ v i ∈ V ( G ) deg G ( v i ) e G ( v i ) , ξ c e ( G ) = ∑ v i ∈ V ( G ) deg G ( v i ) e G ( v i ) where deg G ( v i ) is the degree of v i in G and e G ( v i ) denotes the eccentricity of vertex v i in G . In this paper we study on the difference of ECI and CEI of graphs G , denoted by ξ D ( G ) = ξ c ( G ) − ξ c e ( G ) . We determine the upper and lower bounds on ξ D ( T ) and the corresponding extremal trees among all trees of order n . Moreover, the extremal trees with respect to ξ D are completely characterized among all trees with given diameter d . And we also characterize some extremal general graphs with respect to ξ D . Finally we propose that some comparative relations between CEI and ECI are proposed on general graphs with given number of pendant vertices.

In the present paper, we compare the geometric–arithmetic index G A and the chromatic number χ of a connected graph with given order. We prove, among other results, an upper bound on the ratio G A ∕ χ . We also prove lower bounds on the chromatic number in terms of geometric–arithmetic index and number of vertices of a connected graph. The results obtained for the chromatic number χ are extended to the clique number ω .

This paper brings together two concepts in the theory of graph colourings: edge or total colourings distinguishing adjacent vertices and those breaking symmetries of a graph. We introduce a class of automorphisms such that edge colourings breaking them are connected to edge colouring distinguishing neighbours by multisets or sums. We call an automorphism of a graph G small if there exists a vertex of G that is mapped into its neighbour. The small distinguishing index of G , denoted D s ′ ( G ) , is the least number of colours in an edge colouring of G such that there does not exist a small automorphism of G preserving this colouring. We prove that D s ′ ( G ) ≤ 3 for every graph G without K 2 as a component, thus supporting, in a sense, the 1-2-3 Conjecture of Karonski, Łuczak and Thomason. We also consider an analogous problem for total colourings in connection with the 1-2 Conjecture of Przybylo and Woźniak.

Given a complete multipartite graph G , we explicitly formulate the effective resistance distance between any two vertices of G , using methods from linear algebra. The Kirchhoff index and the degree Kirchhoff index are defined in terms of the effective resistance distances for any simple graph. In this paper, for G , the exact formulae for the two indices are provided. Along with these results, we obtain the optimal Kirchhoff index and the optimal degree Kirchhoff index.

In interconnection networks, matching preclusion is a measure of robustness when there is a link failure. Let G be a graph with an even number of vertices. The matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching, and the conditional matching preclusion number of G is the minimum number of edges whose deletion results in a graph with no isolated vertices and without a perfect matching. In this paper, we study these problems for undirected binary de Bruijn graph U B ( n ) . As an essential preparation, we obtain conditional edge-fault Hamiltonicity of binary de Bruijn graph B ( n ) . Then we obtain matching preclusion number and conditional matching preclusion number of U B ( n ) for n ⩾ 4 and classify all optimal matching preclusion sets and optimal conditional matching preclusion sets.

Let G be a graph with n vertices and L ( G ) its Laplacian matrix. Define ρ G = 1 d G L ( G ) to be the density matrix of G , where d G denotes the sum of degrees of all vertices of G . Let λ 1 , λ 2 , … , λ n be the eigenvalues of ρ G . The von Neumann entropy of G is defined as S ( G ) = − ∑ i = 1 n λ i log 2 λ i . In this paper, we establish a lower bound and an upper bound to the von Neumann entropy for random multipartite graphs.

The minimum sum coloring problem ( M S C P ) is a vertex coloring problem in which a weight is associated with each color. Its aim is to find a coloring of the vertices of a graph G with the minimum sum of the weights of the used colors. The M S C P has important applications in the fields such as scheduling and VLSI design. The minimum number of colors among all optimal solutions of the M S C P for G is called the chromatic strength of G and is denoted by s ( G ) . A tight upper bound of s ( G ) allows to significantly reduce the search space when solving the M S C P . In this paper, we propose and empirically evaluate two new upper bounds of s ( G ) for general graphs, U B A and U B S , based on an abstraction of all possible colorings of G formulated as an ordered set of decreasing positive integer sequences. The experimental results on the standard benchmarks DIMACS and COLOR show that U B A is competitive, and that U B S is significantly tighter than those previously proposed in the literature for 70 graphs out of 74 and, in particular, reaches optimality for 8 graphs. Moreover, both U B A and U B S can be applied to the more general optimum cost chromatic partition ( O C C P ) problem.

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that for any pair of adjacent vertices, the set of colors appearing on the vertex and incident edges are different. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by χ a ′ ′ ( G ) . Let G be a graph, and χ ( G ) and χ ′ ( G ) be the chromatic number and edge chromatic number of G , respectively. In this paper we show that χ a ′ ′ ( G ) ≤ χ ( G ) + χ ′ ( G ) − 1 for any graph G with χ ( G ) ≥ 6 , and χ a ′ ′ ( G ) ≤ χ ( G ) + Δ ( G ) for any graph G . Our results improve the only known upper bound 2 Δ obtained by Huang et al. (2012). As a direct consequence, we have χ a ′ ′ ( G ) ≤ Δ ( G ) + 3 if χ ( G ) = 3 and thus it implies the known results on graphs with maximum degree 3, K 4 -minor-free graphs, outerplanar graphs, graphs with maximum average degree less than 3, planar graphs with girth at least 4 and 2-degenerate graphs.

The Maximum Independent Set Problem is known to be NP-hard in general. In the last decades lots of effort were spent to find polynomial-time algorithms for P t -free graphs. A recent result presents such an algorithm for P 5 -free graphs. On the other hand, the complexity status for larger t is still unknown. In this paper we present a subexponential algorithm for the Maximum (Weighted) Independent Set Problem in P t -free graphs.

Let G be a simple graph with vertex set V ( G ) . A set S ⊆ V ( G ) is independent if no two vertices from S are adjacent. The graph G is known to be Konig–Egervary if α ( G ) + μ ( G ) = | V ( G ) | , where α ( G ) denotes the size of a maximum independent set and μ ( G ) is the cardinality of a maximum matching. A nonempty collection Γ of maximum independent sets is Konig–Egervary if | ⋃ Γ | + | ⋂ Γ | = 2 α ( G ) (Jarden et al., 2015). In this paper, we prove that G is a Konig–Egervary graph if and only if for every two maximum independent sets S 1 , S 2 of G , there is a matching from V ( G ) − S 1 ∪ S 2 into S 1 ∩ S 2 . Moreover, the same is true, when instead of two sets S 1 and S 2 we consider an arbitrary Konig–Egervary collection.

In 1965, Jack Edmonds proposed his celebrated polynomial-time algorithm to find a maximum matching in a graph. It is well-known that finding a maximum matching in G is equivalent to finding a maximum independent set in the line graph of G . For general graphs, the maximum independent set problem is NP-hard. What makes this problem easy in the class of line graphs and what other restrictions can lead to an efficient solution of the problem? In the present paper, we analyse these and related questions. We also review various techniques that may lead to efficient algorithms for the maximum independent set problem in restricted graph families, with a focus given to augmenting graphs and graph transformations. Both techniques have been used in the solution of Edmonds to the maximum matching problem, i.e. in the solution to the maximum independent set problem in the class of line graphs. We survey various results that exploit these techniques beyond the line graphs.

The P I index of a graph G is defined by P I ( G ) = ∑ e = ( u , v ) ∈ E [ m u ( e | G ) + m v ( e | G ) ] where m u ( e | G ) be the number of edges in G lying closer to vertex u than to vertex v and m v ( e | G ) be the number of edges in G lying closer to vertex v than to vertex u . In this paper, we give the upper and lower bounds on the P I index of connected unicyclic and bicyclic graphs with given girth and completely characterize the corresponding extremal graphs. From our results, it is easy to get the bounds and extremal graphs of the unicyclic and bicyclic graphs.

Let G n , m be the set of all connected bipartite graphs of order n and size m . In this paper, the problem on maximum Laplacian spectral radius of graphs in G n , m is considered. Among G n , m with n ⩽ m ⩽ 2 n − 5 , the largest Laplacian spectral radius of graphs is determined. As well the upper bound on Laplacian spectral radius of graphs among G n , l ( n − l ) with 2 ⩽ l ⩽ ⌊ n 2 ⌋ is determined. All the corresponding extremal graphs are characterized, respectively.

Based on electrically equivalent transformations on weighted graphs, in this paper, we present a formula for computing the number of spanning trees of a family of 2-separable graphs formed from two base graphs by 2-sum operations. As applications, we compute the number of spanning trees of some special 2-separable graphs. Then comparisons are made between the number of spanning trees and the number of acyclic orientations for this family of 2-separable graphs under certain constraints. We also show that a factorization formula exists for the sum of weights of spanning trees of a special splitting graph.

The matching preclusion number of a graph is the minimum number of edges whose deletion results the remaining graph that has neither perfect matchings nor almost perfect matchings. In this paper, we prove that the matching preclusion number of k -ary n -cubes is 4 n − 1 except k = 3 and n = 2 , where k is odd and k ≥ 3 .

The Fibonacci word F is the fixed point beginning with a of morphism σ ( a ) = a b and σ ( b ) = a . Since F is uniformly recurrent, each factor ω appears infinitely many times in the sequence which is arranged as ω p (the p th occurrence of ω , p ≥ 1 ). Here we distinguish ω p ≠ ω q if p ≠ q . In this paper, we give an algorithm for counting the number of repeated palindromes in F [ 1 , n ] (the prefix of F of length n ). That is the number of the pairs ( ω , p ) , where ω is a palindrome and ω p ≺ F [ 1 , n ] . We also get explicit expressions for some special n such as n = f m (the m th Fibonacci number). Similar results are also given for the Tribonacci word, the fixed point beginning with a of morphism τ ( a ) = a b , τ ( b ) = a c and τ ( c ) = a .

The idea of the inverse optimization problem is to adjust the value of the parameters such that the observed feasible solution becomes optimal. The modification cost can be measured by different norms, such as l 1 , l 2 , l ∞ norms and the Hamming distance, and the goal is to adjust the parameters as little as possible. In this paper, we consider the inverse minimum flow problem under the weighted sum-type Hamming distance, where the lower and upper bounds for the arcs should be changed as little as possible under the weighted sum-type Hamming distance such that a given feasible flow becomes a minimum flow. Two models are considered: the unbounded case and the general bounded case. We present their respective combinatorial algorithms that both run in O ( n m ) time in terms of the minimum cut method. Computational examples are presented to illustrate our algorithms.

A median (antimedian) of a profile of vertices on a graph G is a vertex that minimizes (maximizes) the sum of the distances to the elements in the profile. The median (antimedian) function has as output the set of medians (antimedians) of a profile. It is one of the basic models for the location of a desirable (obnoxious) facility in a network. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper an axiomatic characterization is obtained for the median and antimedian function on complete graphs minus a matching.

In this paper, we have shown that a graph is a circular arc graph if and only if the corresponding symmetric digraph with loops is a circular arc digraph. We characterize circular arc digraphs and circular arc graphs using circular ordering of their edges. We also characterize a circular arc graph as a union of an interval graph and a threshold graph. Finally, we characterize proper interval bigraphs and proper circular arc bigraphs using two linear orderings of their vertex set.

The paper investigates relationship between algebraic expressions and two-terminal directed acyclic graphs. We consider rhomboidal non-series–parallel graphs, specifically, a digraph called a full square rhomboid. Our intention is to simplify the expressions of full square rhomboids. We describe two decomposition methods for generating expressions of rhomboidal graphs and carry out their comparative analysis.

For a simple graph G with n -vertices, m edges and having signless Laplacian eigenvalues q 1 , q 2 , … , q n , the signless Laplacian energy Q E ( G ) of the graph G is defined as Q E ( G ) = ∑ i = 1 n ∣ q i − d ¯ ∣ , where d ¯ = 2 m n is the average degree of G . In this paper, we obtain the lower and upper bounds for the signless Laplacian energy Q E ( G ) in terms of clique number ω , maximum degree Δ , number of vertices n , first Zagreb index M 1 ( G ) and number of edges m . As an application, we obtain the bounds for the energy of line graph ℒ ( G ) of a graph G in terms of various graph parameters. We also obtain a relation between the signless Laplacian energy Q E ( G ) and the incidence energy I E ( G ) .

A graph G is said to be quasi- λ -distance-balanced if for every pair of adjacent vertices u and v , the number of vertices that are closer to u than to v is λ times bigger (or λ times smaller) than the number of vertices that are closer to v than to u , for some positive rational number λ > 1 . This paper introduces the concept of quasi- λ -distance-balanced graphs, and gives some interesting examples and constructions. It is proved that every quasi- λ -distance-balanced graph is triangle-free. It is also proved that the only quasi- λ -distance-balanced graphs of diameter two are complete bipartite graphs. In addition, quasi- λ -distance-balanced Cartesian and lexicographic products of graphs are characterized. Connections between symmetry properties of graphs and the metric property of being quasi- λ -distance-balanced are investigated. Several open problems are posed.

A Nordhaus–Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In Henning et al. (2011) the authors (Henning et al.) show that if G 1 ⊕ G 2 = K ( s , s ) , and neither G 1 nor G 2 has isolated vertices, then the product γ t ( G 1 ) γ t ( G 2 ) is at most max { 8 s , ⌊ ( s + 6 ) 2 ∕ 4 ⌋ } , where γ t is the total domination number. In this paper we will use a vertex disjoint star covering technique, to significantly improve the mentioned bound. In particular, we will show that if G 1 ⊕ G 2 = K ( s , s ) , and neither G 1 nor G 2 has isolated vertices, then γ t ( G 1 ) γ t ( G 2 ) ≤ max { 8 s , ⌊ ( s + 5 ) 2 ∕ 4 ⌋ } .

Let q ( G ) and μ ( G ) denote the signless Laplacian and distance signless Laplacian spectral radius of a digraph G , respectively. In this paper, we characterize the extremal digraph which has the maximum signless Laplacian spectral radius among all strongly connected digraphs with given dichromatic number. We also determine the extremal digraph having the minimum distance signless Laplacian spectral radius among all strongly connected digraphs with given vertex connectivity.

The first multiplicative Zagreb index of a graph G is the product of the square of every vertex degree, while the second multiplicative Zagreb index is the product of the products of degrees of pairs of adjacent vertices. In this paper, we explore the trees in terms of given number of vertices of maximum degree. The maximum and minimum values of ∏ 1 ( G ) and ∏ 2 ( G ) of trees with arbitrary number of maximum degree are provided. In addition, the corresponding extremal graphs are characterized.

The present paper is devoted to estimating effective resistances in large weighted undirected Cayley graph Cay ( S n , T n ) on symmetric group S n . We obtain asymptotically exact bounds for minimal resistances in Cay ( S n , T n ) . Maximal and average resistances in Cayley graphs on symmetric groups are given in terms of degree, girth and spectral gap. Sharp asymptotic bounds for maximal and average resistances are obtained for star and transposition Cayley graphs. Finally, we find improved estimates of effective resistances in bubble-sort Cayley graphs.

A P 3 -decomposition of a directed graph D is a partition of the arcs of D into directed paths of length 2. In this paper, we give a characterization for a tournament and a bipartite digraph admitting a P 3 -decomposition. This solves a problem posed by Diwan (2016).

The problem of avoidance of a single permutation pattern or of a pair of patterns of length four has been well studied. Less is known concerning the avoidance of three 4 -letter patterns. In this paper, we determine up to symmetry all triples of 4 -letter patterns such that the number of members of S n avoiding any one of them is given by the binomial transform of Fine’s sequence (see A033321 in OEIS). We make use of both algebraic and combinatorial proofs in order to establish our results. In a couple of cases, we introduce certain auxiliary statistics on S n which give rise to a system of functional equations that can be solved using the kernel method. In another case, a direct bijection is defined between members of the avoidance class in question and the set of skew Dyck paths.

Considering an integer k and a directed, weighted graph with two distinct nodes s and t, the Hop-Constrained Shortest Path Problem looks for a shortest (s,t)-path using at most k arcs. In this paper, we study the polytope of the convex hull of incidence vectors of (s,t)-paths using at most k arcs. We present valid inequalities and adaptations of known concepts such as cloning and a unique representation of facets. The main focus will be on one particular family of valid inequalities, the family of Jump Inequalities. Thereby, the main contribution will be a characterization of the members of the family inducing facets. Furthermore, all possibilities to lift the remaining inequalities will be defined. The analysis of Jump Inequalities will be concluded by further results concerning the equivalence of inequalities as well as their Chvtal rank.

In 1965, Motzkin–Straus established the connection between the maximum cliques and the Lagrangian of a graph, the maximum value of a quadratic function determined by a graph in the standard simplex. This connection gave a proof of the Turan’s classical result on Turan densities of complete graphs. In 1980’s, Sidorenko and Frankl–Furedi further developed this method for hypergraph Turan problems. However, the connection between the Lagrangian and the maximum cliques of a graph cannot be extended to hypergraphs. In 2009, S. Rota Bulo and M. Pelillo defined a homogeneous polynomial function of degree r determined by an r -uniform hypergraph and gave the connection between the minimum value of this polynomial function and the maximum cliques of an r -uniform hypergraph. In this paper, we provide a connection between the local (global) minimizers of non-homogeneous polynomial functions to the maximal (maximum) cliques of hypergraphs whose edges containing r − 1 and r vertices. This connection can be applied to obtain an upper bound on the Turan densities of complete { r − 1 , r } -type hypergraphs.

A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence ( n 1 , … , n k ) of positive integers with n 1 + … + n k = n , there exists a partition ( V 1 , … , V k ) of the vertex set V ( G ) such that V i induces a connected subgraph of order n i , for i = 1 , … , k . In this paper we consider the on-line version of this notion, defined in a natural way. We prove that if G is a connected graph such with the independence number at most ⌈ n 2 ⌉ and the degree sum of any pair of non-adjacent vertices is at least n − 3 , then G is on-line arbitrarily partitionable except for two graphs of small orders. We also prove that if G is a connected graph of order n and size ‖ G ‖ > n − 3 2 + 6 , then G is on-line AP unless n is even and G is a spanning subgraph of a unique exceptional graph. These two results imply that dense AP graphs satisfying one of the above two assumptions are also on-line AP. This is in contrast to sparse graphs where only few AP graphs are also on-line AP.

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. In this paper, we have obtained bounds for the b-chromatic number of powers of Qn, namely Qnp, for n5 and n2

Recently, the concept of coarseness was introduced as a measure of how blended a 2-colored point set S is. In the definition of this measure, a convex partition , that is, a partition of S into sets {S1,,Sk} of S whose convex hulls are pairwise disjoint, is considered. The discrepancy of , denoted by d(S,), is the smallest (bichromatic) discrepancy of the elements of . The coarseness of S, denoted by C(S), is then defined as the maximum of d(S,) over all convex partitions of S. Roughly speaking, the value of the coarseness is high when we can split S into blocks, each with large discrepancy. It has been conjectured that computing the coarseness is NP-hard. In this paper, we study how to compute the coarseness for two constrained cases: (1) when the k elements of are separated by k1 pairwise parallel lines (strips) and, (2) the case in which the cardinality of the partition is fixed and the elements of are covered by pairwise disjoint axis-aligned rectangles (boxes). For the first case we present an O(n2log2n)-time algorithm, and show that such a computation problem is 3SUM-hard; for the second, we show that computing the coarseness with k boxes is NP-hard, when k is part of the input. For k fixed, we show that the coarseness can be computed in O(n2k1) time and propose more efficient algorithms for k=2,3,4.

Given a graph that contains an invisible fugitive, the fast searching problem is to find the fast search number, i.e., the minimum number of searchers to capture the fugitive in the fast search model. In this paper, we give a new lower bound on the fast search number. Using the new lower bound, we prove an explicit formula for the fast search number of the Cartesian product of an Eulerian graph and a path. We also give formulas for the fast search number of variants of the Cartesian product. We present an upper bound on the fast search number of hypercubes, and extend the results to a broader class of graphs including toroidal grids.

In this paper, we study graphs whose matching polynomials have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We characterize all matching integral traceable graphs. We show that apart from K7(E(C3)E(C4)) there is no connected k-regular matching integral graph if k2. It is also shown that if G is a graph with a perfect matching, then its matching polynomial has a zero in the interval (0,1]. Finally, we describe all claw-free matching integral graphs.

It is known that Total Coloring Conjecture (TCC) was verified for planar graphs with maximum degree 6. In this paper, we prove that TCC holds for planar graphs G with (G)=6, if G does not contain any subgraph isomorphic to a 4-fan.

With any (not necessarily proper) edge k-colouring :E(G){1,,k} of a graph G, one can associate a vertex colouring given by (v)=ev(e). A neighbour-sum-distinguishing edge k-colouring is an edge colouring whose associated vertex colouring is proper. The neighbour-sum-distinguishing index of a graph G is then the smallest k for which G admits a neighbour-sum-distinguishing edge k-colouring. These notions naturally extend to total colourings of graphs that assign colours to both vertices and edges.We study in this paper equitable neighbour-sum-distinguishing edge colourings and total colourings, that is colourings for which the number of elements in any two colour classes of differ by at most one. We determine the equitable neighbour-sum-distinguishing index of complete graphs, complete bipartite graphs and forests, and the equitable neighbour-sum-distinguishing total chromatic number of complete graphs and bipartite graphs.

The general sum-connectivity index of a graph G is defined as (G)=uvE(G)(d(u)+d(v)), where d(u) denotes the degree of a vertex u in G and is a real number. In this paper, we present the maximum general sum-connectivity indices of trees and chemical trees with given number of pendent vertices for 1

In a finite undirected graph G , a vertex dominates itself and all its neighbors in G . A vertex set D is an efficient dominating set ( e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D . The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G , is known to be NP -complete even for very restricted graph classes such as P 7 -free chordal graphs; its complexity was an open question for P 6 -free graphs and was open even for the subclass of P 6 -free chordal graphs. Recently, Lokshtanov et al., and independently, Brandstadt and Mosca showed that ED is solvable in polynomial time for P 6 -free graphs. The ED problem on a graph G can be reduced to the Maximum Weight Independent Set problem on the square of G . In this paper, we show that squares of P 6 -free chordal graphs that have an e.d. are chordal; this even holds for the larger class of ( P 6 , house, hole, domino)-free graphs. Thus, ED/WeightedED is solvable in polynomial time for ( P 6 , house, hole, domino)-free graphs, and in particular, for P 6 -free chordal graphs. Also, the time bound achieved for ED on this class is much better than in the P 6 -free case. Moreover, we show that squares of P 6 -free graphs that have an e.d. are hole-free. Based on this result, we show that ED is solvable in polynomial time for ( P 6 , net)-free graphs; again, the time bound for ED on this class is much better than in the P 6 -free case.

This paper studies the choice number and paint number of the lexicographic product of graphs. We prove that if $G$ has maximum degree $\Delta$, then for any graph $H$ on $n$ vertices $ch(G[H]) \le (4\Delta+2)(ch(H) +\log_2 n)$ and $\chi_P(G[H]) \le (4\Delta+2) (\chi_P(H)+ \log_2 n)$.

Finding sufficient conditions for some properties of graphs in light of quantitative methods is an important problem. In this paper, in terms of the Wiener index or Harary index, we present several sufficient conditions for a graph to be k -connected, β -deficient, k -hamiltonian, k -path-coverable or k -edge-hamiltonian.

The class of Boolean functions, which can never occur as output of a faulty combinational circuit, is known as Impossible Class of Faulty Functions (ICFF). Despite years of research, the characterization of ICFF for a complex logic network is yet a significantly open problem. In a recent work (Das et al., 2014), a partial characterization of ICFF was done by completely enumerating a subclass of ICFFs, also called the root functions. For 2 -level AND-OR logic networks for up to 6 -variable the root functions were completely enumerated. This paper significantly extends this line of research by providing a more general framework for handling this class of functions. Both the upper and lower bounds are derived and the maximum cardinality of the weight of non-affine root functions is established. A constructive method for obtaining non-affine root functions of maximum possible weight is provided and it is shown that there are no other such functions than those obtained by our method. The direct correspondence of these functions to the independent dominating sets in the n -dimensional hypercube G n is used for establishing new results concerning the minimum weight of these functions. In particular, we give the exact value of the minimum cardinality of independent dominating set in G n for any n = 2 r − 1 , where r ≥ 2 . Since our approach is also constructive, we essentially efficiently solve this problem for any n = 2 r − 1 , where r ≥ 2 , and our results conform to the observation of Harary and Livingston (2010). Finally, the problem of classifying and enumerating root functions is addressed leading to some non-trivial lower bounds on their number, though the problem appears to be hard and further research in this direction is needed.

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S . We study cubic graphs whose vertex set can be partitioned into two total dominating sets. There are infinitely many examples of connected cubic graphs that do not have such a vertex partition. In this paper, we show that the class of claw-free cubic graphs has such a partition. For an integer k at least 3 , a graph is k -chordal if it does not have an induced cycle of length more than k . Chordal graphs coincide with 3 -chordal graphs. We observe that for k ≥ 6 , not every graph in the class of k -chordal, connected, cubic graphs has two vertex disjoint total dominating sets. We prove that the vertex set of every 5 -chordal, connected, cubic graph can be partitioned into two total dominating sets. As a consequence of this result, we observe that this property also holds for a connected, cubic graph that is chordal or 4 -chordal. We also prove that cubic graphs containing a diamond as a subgraph can be partitioned into two total dominating sets.

In this paper, we study the spectra of weighted digraphs, where weights are taken from the set of non zero real numbers. We obtain formulae for the characteristic polynomial of two families of weighted bipartite digraphs. We study the sign alternating property of coefficients of characteristic polynomial in some classes of weighted digraphs. We extend the concept of energy to weighted digraphs and obtain Coulson's integral formula. As a consequence of these results, we study energy comparison property by means of a quasi-order relation. Unicyclic weighted digraphs with cycle-weight r is an element of [-1, 1] \ {0} having minimum and maximum energy are characterized. Finally, we obtain well known McClelland upper bound for the energy of weighted digraphs and also an upper bound for the energy of a weighted digraph in terms of number of arcs and their weights. (C) 2017 Elsevier B.V. All rights reserved.

An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial-time solvable when restricted to trees or series–parallel graphs. In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number.

The proximity of a graph G is the minimum average distance from a vertex of G to all others. Similarly, the remoteness of G is the maximum average distance from a vertex to all others. The girth g of a graph G is the length of its smallest cycle. In this paper, we provide and prove sharp lower and upper bounds, in terms of the order n of G, on the difference, the sum, the ratio and the product of the proximity and the girth. We do the same for the remoteness and the girth, except for the lower bound on /g, which is already known.

Let G σ be an oriented graph with skew adjacency matrix S ( G σ ) . The skew energy E S ( G σ ) of G σ is the sum of the norms of all eigenvalues of S ( G σ ) and the skew rank s r ( G σ ) of G σ is the rank of S ( G σ ) . In this paper, it is proved that E S ( G σ ) ≥ 2 μ ( G ) for an arbitrary connected oriented graph G σ of order n , where μ ( G ) is the matching number of G , and the equality holds if and only if G is a complete bipartite graph K n 2 , n 2 with partition ( X , Y ) of equal size and σ is switching-equivalent to the elementary orientation of G which assigns all edges the same direction from vertices of X to vertices of Y . As an application, we prove that E S ( G σ ) ≥ s r ( G σ ) for an oriented graph G σ and the equality holds if and only if G is the disjoint union of some copies of K 2 and some isolated vertices.

In this paper it is shown that the characterizations of trees and unicyclic graphs having a given matching number and minimum connectivity index 12, proposed by Du et al. (2010) remain valid for general connectivity index if 1

For positive integers k and r, a (k,r)-coloring of a graph G is a proper coloring of the vertices with k colors such that every vertex of degree i will be adjacent to vertices with at least min{i,r} different colors. The r-dynamic chromatic number of G, denoted by r(G), is the smallest integer k for which G has a (k,r)-coloring. For a k-list assignment L to vertices of G, an (L,r)-coloring of G is a coloring c such that for every vertex v of degree i, c(v)L(v) and v is adjacent to vertices with at least min{i,r} different colors. The list r-dynamic chromatic number of G, denoted by L,r(G), is the smallest integer k such that for every k-list L, G has an (L,r)-coloring.In this paper, the behavior and bounds of 3-dynamic coloring and list 3-dynamic coloring of K1,3-free graphs are investigated. We show that if G is K1,3-free, then L,3(G)max{L(G)+3,7} and 3(G)max{(G)+3,7}. The results are best possible as 7 cannot be reduced.

The minimum vertex cover problem and the minimum vertex partition problem are central problems in graph theory and many generalisations are known. Two examples are the minimumk-path vertex cover problem (MkPVCP for short), which asks for a minimum set of vertices covering every path of order k, and the minimumk-path partition problem (MkPPP for short), which asks for a minimum set of paths in a maximal path packing whose every path has at most k vertices.In this paper, we will present a relation between the MkPPP and the MkPVCP. Based on it, we will obtain new bounds for their invariants and a new sufficient condition for NP-hardness of the MkPVCP in terms of forbidden subgraphs.