Search

Given the Kekulé structure of a fullerene that gives its Clar structure, the Kekulé edges that do not lie on any benzene ring of the Clar structure lie on open chains that pair up the pentagonal faces and perhaps some closed chains. In this paper, we introduce Fries chains and show that given the Kekulé structure of a fullerene that gives its Fries structure, the Kekulé edges that do not lie on two benzene rings lie on the union of a set of these Fries chains. The edges that lie on exactly one benzene ring belong to exactly one of these chains while edges that lie on no benzene ring belong to exactly two of these chains. We will see that the Fries chains will include the Clar chains in some cases and will be quite distinct from the Clar chains in other cases. Examples of fullerenes with the property that the set of benzene rings that give its Clar number are not a subset of the benzene rings that give its Fries number have been known for a few years. However, in all of these known examples, almost all of the benzene rings of its Clar structure are among benzene rings of its Fries structure. In this paper, we describe a class of fullerenes with the property that the set of benzene rings of its Clar structure and the set of benzene rings of its Fries structure practically disjoint. [ABSTRACT FROM AUTHOR]

A graph G = ( V , E ) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if ( x , y ) ∈ E for each x ≠ y . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n , while there exist graphs for which it is n / 2 . [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the basic homogeneous -machine scheduling problem where weakly dependent unit-time jobs have to be scheduled within the time windows between their release dates and due dates so that, for any subset of machines, the set of the time units at which at least one machine is busy, is in interval. We first introduce the notions of pyramidal structure, -hole, -matching, preschedule, -schedule and schedule for this problem. Then we provide a feasibility criteria for a preschedule. The key result of the paper is then to provide a structural necessary and sufficient condition for an instance of the problem to be feasible. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling -machine scheduling problem. [Copyright &y& Elsevier]

Abstract: Let be a family of subsets of an -element set. Sperner’s theorem says that if there is no inclusion among the members of then the largest family under this condition is the one containing all -element subsets. The present paper surveys certain generalizations of this theorem. The maximum size of is to be found under the condition that a certain configuration is excluded. The configuration here is always described by inclusions. More formally, let be a poset. The maximum size of a family which does not contain as a (not-necessarily induced) subposet is denoted by . The paper is based on a lecture of the author at the Jubilee Conference on Discrete Mathematics [Banasthali University, January 11–13, 2009], but it was somewhat updated in December 2010. [Copyright &y& Elsevier]

Abstract: This paper studies the ambiguity of morphisms in free monoids. A morphism is said to be ambiguous with respect to a string if there exists a morphism which differs from for a symbol occurring in , but nevertheless satisfies ; if there is no such then is called unambiguous. Motivated by the recent initial paper on the ambiguity of morphisms, we introduce the definition of a so-called segmented morphism , which, for any , maps every symbol in an infinite alphabet onto a word that consists of distinct factors in , where and are different letters. For every , we consider the set of those finite strings over an infinite alphabet with respect to which is unambiguous, and we comprehensively describe its relation to any , . Thus, our work features the first approach to a characterisation of sets of strings with respect to which certain fixed morphisms are unambiguous, and it leads to fairly counter-intuitive insights into the relations between such sets. Furthermore, it shows that, among the widely used homogeneous morphisms, most segmented morphisms are optimal in terms of being unambiguous for a preferably large set of strings. Finally, our paper yields several major improvements of crucial techniques previously used for research on the ambiguity of morphisms. [Copyright &y& Elsevier]

A half-space over a distance space is a generalization of a half-space in a vector space. An important advantage of a distance space over a metric space is that the triangle inequality need not be satisfied, which makes our results potentially very useful in practice. Given two points in a set, a half-space is defined by them, as the set of all points closer to the first point than to the second. In this paper we consider the problem of learning half-spaces in any finite distance space, that is, any finite set equipped with a distance function. We make use of a notion of ‘width’ of a half-space at a given point: this is defined as the difference between the distances of the point to the two points that define the half-space. We obtain probabilistic bounds on the generalization error when learning half-spaces from samples. These bounds depend on the empirical error (the fraction of sample points on which the half-space does not achieve a large width) and on the VC-dimension of the effective class of half-spaces that have a large sample width. Unlike some previous work on learning classification over metric spaces, the bound does not involve the covering number of the space, and can therefore be tighter. [ABSTRACT FROM AUTHOR]

In this paper, we study four games, they are all restrictions of ( s , t ) -Wythoff’s game which was introduced by A.S. Fraenkel. The first one is a modular type restriction of ( s , t ) -Wythoff’s game, where a player is restricted to remove a multiple of K tokens in each move ( K is a fixed positive integer). The others we called rook type restrictions of ( s , t ) -Wythoff’s game, including Odd-Arbitrary-Nim ( s , t ) -Wythoff’s Game, Odd–Odd-Nim ( s , t ) -Wythoff’s Game and Odd–Even-Nim ( s , t ) -Wythoff’s Game. In these three games, the restrictions are only made on horizontal and vertical moves, but not on the extended diagonal moves. For any K , s , t ≥ 1 , the sets of P -positions of our games are given in both normal and misère play. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Let E be a set of points in F q d . Bennett et al. (2016) proved that if | E | ≫ q d − d − 1 k + 1 then E determines a positive proportion of all k -simplices. In this paper, we give an improvement of this result in the case when E is the Cartesian product of sets. Namely, we show that if E is the Cartesian product of sets and q k d k + 1 − 1 ∕ d = o ( | E | ) , the number of congruence classes of k -simplices determined by E is at least ( 1 − o ( 1 ) ) q k + 1 2 , and in some cases our result is sharp. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with vertex set V , minimum degree δ and edge-connectivity λ . If α is a real number, then the zeroth-order general Randić index is defined by ∑ x ∈ V deg α ( x ) , where deg ( x ) denotes the degree of the vertex x . A graph is maximally edge-connected if λ = δ . In this paper, we present sufficient conditions for connected graphs (resp. connected triangle-free graphs) to be maximally edge-connected in terms of the zeroth-order general Randić index, the order and the minimum degree when α ∈ ( − ∞ , 0 ) or α ∈ ( 1 , 2 ] (resp. α ∈ [ − 1 , 0 ) ∪ ( 1 , 2 ] ). [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a graph with no isolated vertex. A subset of vertices S is a total dominating set if every vertex of G is adjacent to some vertex of S . For some α with 0 < α ≤ 1 , a total dominating set S in G is an α -total dominating set if for every vertex v ∈ V ∖ S , | N ( v ) ⋂ S | ⩾ α | N ( v ) | . The α -total domination number of G , denoted by γ α t ( G ) , is the minimum cardinality of an α -total dominating set of G . In Henning and Rad (2012), Henning and Rad posed the following question: Let G be a connected cubic graph with order n . Is it true that γ α t ( G ) ≤ 3 n 4 for 2 3 < α ≤ 1 ? In this paper, we give a positive answer toward this question. Furthermore, we give a characterization on cubic graphs attaining the bound for the α -total domination number. [ABSTRACT FROM AUTHOR]

In their celebrated paper, Erdos et al. (1961) posed the following question. Let F be a family of k -element subsets of an n -element set satisfying the condition that | F ∩ G | ≥ ℓ holds for any two members of F where ℓ ≤ k are fixed positive integers. What is the maximum size | F | of such a family? They gave a complete solution for the case ℓ = 1 : the largest family is the one consisting of all k -element subsets containing a fixed element of the underlying set. (One has to suppose 2 k ≤ n , otherwise the problem is trivial.) They also proved that the best construction for arbitrary ℓ is the family consisting of all k - element subsets containing a fixed ℓ -element subset, but only for large n ’s. They also gave an example showing that this statement is not true for small n ’s. Later Frankl gave a construction for the general case that he believed to be the best. Frankl, Wilson and Füredi made serious progress towards the proof of this conjecture, but the complete solution was not achieved until 1996 when the surprising news came: Rudolf Ahlswede and Levon Khachatrian have found the proof. They invented the expressive name: Complete Intersection Theorem. We will show some of the consequences of this deep and important theorem. [ABSTRACT FROM AUTHOR]

Caro and Wei independently showed that the independence number α ( G ) of a graph G is at least ∑ u ∈ V ( G ) 1 d G ( u ) + 1 . In the present paper we conjecture the stronger bound α ( G ) ≥ ∑ u ∈ V ( G ) 2 d G ( u ) + ω G ( u ) + 1 where ω G ( u ) is the maximum order of a clique of G that contains the vertex u . We discuss the relation of our conjecture to recent conjectures and results concerning the independence number and the chromatic number. Furthermore, we prove our conjecture for perfect graphs and for graphs of maximum degree at most 4. [ABSTRACT FROM AUTHOR]

The triangle graph of a graph G , denoted by T ( G ) , is the graph whose vertices represent the triangles ( K 3 subgraphs) of G , and two vertices of T ( G ) are adjacent if and only if the corresponding triangles share an edge. In this paper, we characterize graphs whose triangle graph is a cycle and then extend the result to obtain a characterization of C n -free triangle graphs. As a consequence, we give a forbidden subgraph characterization of graph G for which T ( G ) is a tree, a chordal graph, or a perfect graph. For the class of graphs whose triangle graph is perfect, we verify a conjecture of the third author concerning packing and covering of triangles. [ABSTRACT FROM AUTHOR]

An arc coloring of a digraph D is proper if (i) no two arcs with a common tail receive the same color and (ii) no two arcs with a common head receive the same color. Define the out-arc set and in-arc set of a vertex v of D to be the set of arcs with tail v and the set of arcs with head v , respectively. A proper arc coloring of D is vertex-distinguishing (resp. semi-vertex-distinguishing ) if (i) no two vertices (resp. no three vertices) have the same color set for their in-going arcs and (ii) no two vertices (resp. no three vertices) have the same color set for their out-going arcs. And a proper arc coloring of D is equitable if the numbers of arcs colored by any two colors differ by at most one. In this paper, (semi-)vertex-distinguishing proper arc colorings of digraphs are introduced. Denote by χ v d ′ ( D ) (resp. χ s v d ′ ( D ) ) the minimum number of colors required for a vertex-distinguishing (resp. semi-vertex-distinguishing) proper arc coloring of D . We give upper bounds for χ v d ′ ( D ) and χ s v d ′ ( D ) respectively. In particular, the value of χ v d ′ ( D ) is obtained for some regular digraphs D . Moreover, we show that the values of χ v d ′ ( D ) and χ s v d ′ ( D ) will not be changed if the coloring is, in addition, required to be equitable. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with vertex set V ( G ) . The degree distance of G is defined as D ′ ( G ) = ∑ x ∈ V ( G ) d G ( x ) D G ( x ) , where d G ( x ) is the degree of vertex x , D G ( x ) = ∑ u ∈ V ( G ) d G ( u , x ) and d G ( u , x ) is the distance between u and x . A connected graph G is called a cactus if any two of its cycles have at most one common vertex. Let \xi ( 2 n , r ) be the set of cacti of order 2 n with a perfect matching and r cycles. In this paper, we give the sharp lower bounds of degree distance among \xi ( 2 n , r ) and the corresponding extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

A network is said to be g -conditionally faulty if its every vertex has at least g fault-free neighbors, where g ≥ 1 . An n -dimensional folded hypercube F Q n is a well-known variation of an n -dimensional hypercube Q n , which can be constructed from Q n by adding an edge to every pair of vertices with complementary addresses. F Q n for any odd n is known to be bipartite. In this paper, let F F v denote the set of faulty vertices in F Q n , and let F F Q n ( e ) denote the set of faulty vertices which are incident to the end-vertices of any fault-free edge e ∈ E ( F Q n ) . Then, under the 4-conditionally faulty and | F F Q n ( e ) | ≤ n − 3 , we consider for the vertex-fault-tolerant cycles embedding properties in F Q n − F F v , as follows: 1. For n ≥ 4 , F Q n − F F v contains a fault-free cycle of every even length from 4 to 2 n − 2 | F F v | , where | F F v | ≤ 2 n − 7 ; 2. For n ≥ 4 being even, F Q n − F F v contains a fault-free cycle of every odd length from n + 1 to 2 n − 2 | F F v | − 1 , where | F F v | ≤ 2 n − 7 . [ABSTRACT FROM AUTHOR]

A proper edge colouring of a graph with natural numbers is consecutive if colours of edges incident with each vertex form a consecutive interval of integers. The deficiency d e f ( G ) of a graph G is the minimum number of pendant edges whose attachment to G makes it consecutively colourable. Since all 1-trees are consecutively colourable, in this paper we study the deficiency of k -trees for k ≥ 2 . Our investigation establishes the values of the deficiency of all k -trees that have maximum degree bounded from above by 2 k , with k ∈ { 2 , 3 , 4 } . To obtain these results we consider the structure of k -trees with bounded degree and the deficiency of general graphs of odd order. In the first case we show that for n ≥ 2 k + 3 the structure of an n -vertex k -tree with maximum degree not greater than 2 k is unique. In the second one we prove that for each n -vertex graph G of odd order the inequality d e f ( G ) ≥ 1 2 ( | E ( G ) | − ( n − 1 ) Δ ( G ) ) holds. Both last mentioned results seem to be interesting in their own right. [ABSTRACT FROM AUTHOR]

Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph B S n under the MM model is 6 n − 15 for n ≥ 6 and under the PMC model is 8 n − 21 for n ≥ 5 . [ABSTRACT FROM AUTHOR]

An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane, which is introduced in connection with the defect-tolerant design of nano-circuits. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. A 3-directional orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction. The characterizations and the complexity of the recognition problem have been open for orthogonal ray graphs and 3-directional orthogonal ray graphs, while various characterizations with a quadratic-time recognition algorithm have been known for 2-directional orthogonal ray graphs. In this paper, we show several characterizations with a linear-time recognition algorithm for orthogonal ray trees by using the 2-directional orthogonal ray trees. We also show that a tree is a 3-directional orthogonal ray graph if and only if it is a 2-directional orthogonal ray graph. Moreover, we show some necessary conditions for orthogonal ray graphs and 3-directional orthogonal ray graphs. [ABSTRACT FROM AUTHOR]

In this paper, we show that for all v ≡ 1 (mod 3), there exists a super-simple ( v , 4 , 2 ) directed design. Also, we show that for these parameters there exists a super-simple ( v , 4 , 2 ) directed design whose each defining set has at least a half of the blocks. [ABSTRACT FROM AUTHOR]

In a graph G , an efficient dominating set is a subset D of vertices such that D is an independent set and each vertex outside D has exactly one neighbor in D . The Efficient Dominating Set (ED) problem asks for the existence of an efficient dominating set in a given graph. The ED problem is known to be solvable in polynomial time for P 5 -free graphs but N P -complete for P 7 -free graphs whereas for P 6 -free graphs, its complexity was an open problem. Recently, Lokshtanov et al. and independently, Mosca showed that ED is solvable in polynomial time for P 6 -free graphs. In this paper, we show that the ED problem can be solved efficiently for two subclasses of P 6 -free graphs, namely for ( P 6 , bull)-free graphs, and for ( P 6 , S 1 , 1 , 3 )-free graphs; the time bounds for the two subclasses are much better than in the general case of P 6 -free graphs. [ABSTRACT FROM AUTHOR]

In two-level logic synthesis, the typical input specification is a set of minterms defining the on set and a set of minterms defining the don’t care set of a Boolean function. The problem is to synthesize an optimal set of product terms, or cubes, that covers all the minterms in the on set and some of the minterms in the don’t care set. In this paper, we consider a different specification: instead of the on set and the don’t care set, we are given a set of numbers, each of which specifies the number of minterms covered by the intersection of one of the subsets of a set of λ cubes. We refer to the given set of numbers as an intersection pattern . The problem is to determine whether there exists a set of λ cubes that satisfies the given intersection pattern and, if it exists, to synthesize the set of cubes. We show a necessary and sufficient condition for the existence of λ cubes to satisfy a given intersection pattern. We also show that the synthesis problem can be reduced to the problem of finding a non-negative solution to a set of linear equations and inequalities. [ABSTRACT FROM AUTHOR]

An open-locating-dominating set (OLD-set) is a subset of vertices of a graph such that every vertex in the graph has at least one neighbor in the set and no two vertices in the graph have the same set of neighbors in the set. This is an analogue to the well-studied identifying code in the literature. In this paper, we prove that the optimal density of an OLD-set for the infinite triangular grid is 4 / 13 . [ABSTRACT FROM AUTHOR]

The b -chromatic number of a graph G is the largest integer k such that G has a coloring of the vertices in k color classes such that every color class contains a vertex that has a neighbor in all other color classes. In this paper, we show that for every edge e of a graph G , we have b ( G − e ) ≤ b ( G ) + ⌈ n 2 ⌉ − 2 . Also, we characterize all graphs G for which b ( G − e ) = b ( G ) + ⌈ n 2 ⌉ − 2 for some edge e of G . [ABSTRACT FROM AUTHOR]

In previous papers we have introduced a notion of multivalued continuity in digital spaces which extends the usual notion of digital continuity and allows us to define topological notions, like retractions, in a far more realistic way than by using just single-valued digitally continuous functions. In particular, we have characterized the deletion of simple points in 2-D, one of the most important processing operations in digital topology, as a particular kind of retraction. In this work we extend this result to three-dimensional digital sets, characterizing the deletion of ( 26 , 6 ) -simple points in 3-D as ( N , 26 ) -retractions. [ABSTRACT FROM AUTHOR]

The eccentricity of a vertex v in a graph G is the maximum distance of v from any other vertex of G and v is a contour vertex of G if each vertex adjacent to v has eccentricity not greater than the eccentricity of v . The set of contour vertices of G is geodetic if every vertex of G lies on a shortest path between a pair of contour vertices. In this paper, we firstly investigate the existence of operations on graphs that allow to construct graphs in which the contour is geodetic. Then, after providing an alternative proof of the fact that the contour is geodetic in every HHD-free graph, we show that the contour is geodetic in every cactus and in every graph whose blocks are HHD-free or cycles or cographs. Finally, we generalize the above result by introducing the concept of geodetic-contour-preserving class of graphs and by proving that, if each block B in a graph G belongs to a class GB of graphs which is geodetic-contour-preserving, then the contour of G is geodetic. [ABSTRACT FROM AUTHOR]

A subset F ⊂ V(G) is called a decycling set if the subgraph G−F is acyclic. The minimum cardinality of a decycling set is called the decycling number of G, which is proposed first by Beineke and Vandell (1997). We use ∇(Pn, k) to denote the decycling number of the generalized Petersen graphs Pn, k. This paper proves that ... [ABSTRACT FROM AUTHOR]

Vincular or dashed patterns resemble classical patterns except that some of the letters within an occurrence must satisfy an adjacency requirement. In this paper, we show some general equivalences concerning the avoidance of vincular patterns by multiset permutations. We prove our results by defining bijections between various avoidance classes that preserve the number of occurrences of each letter. As a consequence, we obtain for multiset permutations the complete Wilf-classification of patterns of type (2, 1, 1), which also yields the complete classification for compositions and k-ary words when taken with numerical evidence. [ABSTRACT FROM AUTHOR]

In this paper, we present the clique arrangement A(G) for a chordal graph G to describe the intersections between the maximal cliques of G more precisely than in clique trees or related concepts. In particular, the node set of A(G) contains a node X = C1 ∩ C2 ∩ ... for every set C1, C2, ... of maximal cliques of G. In A(G), there is an arc from a node X to a node Z, if X is a subset of Z and there is no node Y, that is a superset of X and a subset of Z. As clique arrangements may have exponential size, we analyze this notion for strongly chordal graphs G. We provide a new characterization of strongly chordal graphs in terms of forbidden cyclic structures in the corresponding clique arrangements and we show how to compute the clique arrangement of a strongly chordal graph efficiently. [ABSTRACT FROM AUTHOR]

Counting independent sets is a #P-complete problem for general graphs but solvable in polynomial time for interval and permutation graphs. This paper develops some polynomial time algorithms for counting independent sets, maximal independent sets, and independent perfect dominating sets in a tolerance graph, which is a common generalization of interval and permutation graphs. No algorithm for solving those problems for tolerance graphs is currently available. [ABSTRACT FROM AUTHOR]

In this paper, we prove that if a graph G is diamond-free, then the competition number of G is bounded above by 2 + 1/2 ∑v∈Vh(G) (θV(NG(v))−2) where Vh(G) is the set of nonsimplicial vertices of G. This result generalizes Opsut's result for line graphs. We also show that the upper bound holds for certain graphs which might have diamonds. As a matter of fact, we go further to a conjecture that the above upper bound holds for the competition number of any graph, which leads to a natural generalization of Opsut's conjecture. [ABSTRACT FROM AUTHOR]

In this paper we introduce the notion of distance k-guarding applied to triangulation graphs, and associate it with distance k-domination and distance k-covering. We obtain results for maximal outerplanar graphs when k=2. A set S of vertices in a triangulation graph T is a distance 2-guarding set (or 2d-guarding set for short) if every face of T has a vertex adjacent to a vertex of S. We show that ... (respectively, ...) vertices are sufficient to 2d-guard and 2d-dominate (respectively, 2d-cover) any n-vertex maximal outerplanar graph. We also show that these bounds are tight. [ABSTRACT FROM AUTHOR]

A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree Δ has a strong edge-colouring with at most 4 Δ + 4 colours. We show that 3 Δ + 1 colours suffice if the graph has girth 6, and 4 Δ colours suffice if Δ ≥ 7 or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs. [ABSTRACT FROM AUTHOR]

The reciprocal degree distance ( RDD ), defined for a connected graph G as vertex-degree-weighted sum of the reciprocal distances, that is, R D D ( G ) = ∑ u , v ∈ V ( G ) ( d ( u ) + d ( v ) ) d G ( u , v ) . The reciprocal degree distance is a weight version of the Harary index, just as the degree distance is a weight version of the Wiener index. In this paper, the exact formulae for the reciprocal degree distance of tensor product G × K m 0 , m 1 , … , m r − 1 and the strong product G ⊠ K m 0 , m 1 , … , m r − 1 , where K m 0 , m 1 , … , m r − 1 is the complete multipartite graph with partite sets of sizes m 0 , m 1 , … , m r − 1 are obtained. Finally, we apply our result to compute the reciprocal degree distance of open fence and closed fence graphs. [ABSTRACT FROM AUTHOR]

A subset S of vertices of a graph G is called a k -path vertex cover if every path of order k in G contains at least one vertex from S . The cardinality of a minimum k -path vertex cover is called the k -path vertex cover number of a graph G , denoted by ψ k ( G ) . It is known that the minimum k -path vertex cover problem ( k -PVCP) is NP-hard for all k ≥ 2 . In this paper we consider the weighted version of a k -PVCP ( k -WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P k . This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k -WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k -path vertex cover number of a tree with time complexity O ( k ⋅ | V ( G ) | ) is presented. [ABSTRACT FROM AUTHOR]

Two classes of infinite graphs with unbounded vertex degrees are introduced and studied. These are g -tempered and strongly g -tempered graphs, respectively. In such graphs, the degree growth is controlled by a function g : R + → R + . It is proven that for g ( t ) = log t (resp. g ( t ) = t log t ), the number of simple paths of length N originated at a given vertex x (resp. the number of finite connected subgraphs of order N containing x ) is exponentially bounded in N for N belonging to an infinite subset N x ⊂ N , which is a sequence { N k } for g -tempered (resp. { N : N ≥ N x } for strongly g -tempered) graphs. It is shown that the graphs in which the path distance between vertices of large degree is bigger than a certain function of their degrees belong to the classes introduced in this paper. These results are then applied to a number of problems, including estimating volume growth, the growth of the Randić index, and of the number of greedy animals. [ABSTRACT FROM AUTHOR]

In this paper we study the relation between the local spectrum of a vertex set C and the local spectra of its subconstituents. In particular, it is shown that, when C is a completely regular code, such spectra are uniquely determined by the local spectra of C. Moreover, we obtain a new characterization for completely pseudo-regular codes, and consequently for completely regular codes, in terms of the relation between the local spectrum of an extremal set of vertices and the local spectrum of its antipodal set. We also present a new proof of the version of the spectral excess theorem for extremal sets of vertices. [ABSTRACT FROM AUTHOR]

Abstract: The total domination number of a graph is the minimum cardinality of a set of vertices so that every vertex of is adjacent to a vertex in . Our main result of this paper is that if is a connected graph and , then . Furthermore if equality holds in this bound, then the multiset is equal to modulo four. As a consequence of this result, we prove a conjecture on the total domination number. To state this conjecture, let denote the set of vertices of maximum eccentricity in and let denote the maximum distance in of a vertex outside to a vertex of . The following conjecture is known as Graffiti.pc Conjecture #233 (http://cms.dt.uh.edu/faculty/delavinae/research/wowII): if is a connected graph of order at least two, then . We prove this conjecture. In fact, as a consequence of our main result stated earlier we prove the following much stronger result: if is a connected graph of order at least two, then . We also prove that if is a connected graph and , then , and this result is best possible. [Copyright &y& Elsevier]

Abstract: How large can a family be if it does not contain with ? Our aim in this paper is to show that any such family has size at most . This is tight up to a multiplicative constant of 2. We also obtain similar results for families with , showing that they satisfy , where is a constant depending only on . [Copyright &y& Elsevier]

Abstract: A graph is diameter- -critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter- -critical graphs with no induced path on five vertices. Murty and Simon conjectured that the number of edges in a diameter- -critical graph of order is at most and that the extremal graphs are the complete bipartite graphs with partite sets whose cardinality differs by at most one. We use an association with total domination to prove that if is a diameter- -critical graph with no induced path , then is triangle-free. As a consequence, we observe that the Murty–Simon Conjecture is true for -free, diameter-2-critical graphs by Turán’s Theorem. Finally we characterize these graphs by characterizing their complements. [Copyright &y& Elsevier]

Abstract: For a vertex of a graph , let be the set of with all of its neighbors in . A set of vertices is an identifying code of if the sets are nonempty and distinct for all vertices . If admits an identifying code, we say that is identifiable and denote by the minimum cardinality of an identifying code of . In this paper, we study the identifying code of the corona product of graphs and . We first give a necessary and sufficient condition for the corona product to be identifiable, and then express in terms of and the (total) domination number of . Finally, we compute for some special graphs . [Copyright &y& Elsevier]

Abstract: In this paper we take a new approach to the very old problem of aggregating preferences of multiple agents. We define the notion of popular ranking: a ranking of a set of elements is popular if there exists no other permutation of the elements that a majority of the voters prefer. We show that such a permutation is unlikely to exist: we show that a necessary but not sufficient condition for the existence of a popular ranking is Condorcet’s paradox not occurring. In addition, we show that if Condorcet’s paradox does not occur, then we can efficiently compute a permutation, which may or may not be popular, but for which the voters will have to solve an NP-hard problem to compute a permutation that a majority of them prefer. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new characterization of complement Threshold Tolerance graphs (co-TT for short) and find a recognition algorithm for the subclass of split co-TT graphs running in time. Currently, the best recognition algorithms for co-TT graphs and for split co-TT graphs run in time (Hammer and Simeone (1981) [4]; Monma et al. (1988) [7]). [Copyright &y& Elsevier]

Abstract: This paper presents a notion of morphism for resistive electrical networks. One can regard symmetries of a resistive network as morphisms, but they are trivial in the sense that they do not reduce the size of the problem. However, symmetries do induce a nontrivial quotient. We extend this result to arbitrary morphisms in a suitable categorical framework. Our principal application is to solve Kirchoff’s problem for certain products of paths. [Copyright &y& Elsevier]

Abstract: An adjacent vertex distinguishing coloring of a graph is a proper edge coloring of such that any pair of adjacent vertices are incident with distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing coloring of is denoted by . In this paper, we prove that for any graph having maximum degree and no isolated edges. This improves a result in [S. Akbari, H. Bidkhori, N. Nosrati, -strong edge colorings of graphs, Discrete Math. 306 (2006) 3005–3010], which states that for any graph without isolated edges. [Copyright &y& Elsevier]

Abstract: A simple connected undirected graph is called a clustering coefficient locally maximizing graph if its clustering coefficient is not less than that of any simple connected graph obtained from by rewiring an edge, that is, removing an edge and adding a new edge. In this paper, we present some new classes of clustering coefficient locally maximizing graphs. We first show that any graph composed of multiple cliques with orders greater than two sharing one vertex is a clustering coefficient locally maximizing graph. We next show that any graph obtained from a tree by replacing edges with cliques with the same order other than four is a clustering coefficient locally maximizing graph. We also extend the latter result to a more general class. [Copyright &y& Elsevier]

Abstract: A subset in a graph is a -set if, for every vertex , for non-negative integers and , that is, every vertex is adjacent to at least but not more than vertices in . In this paper, we focus on small and , and relate the concept of -sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and -dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph , the restrained domination number is equal to the domination number of . [Copyright &y& Elsevier]

Abstract: A -hypertournament on vertices, where , is a pair , where is the vertex set of and is a set of -tuples of vertices, called arcs, such that, for all subsets with , contains exactly one permutation of as an arc. Gutin and Yeo (1997) showed in [2] that any strong -hypertournament on vertices, where , is Hamiltonian, and posed the question as to whether the result could be extended to vertex-pancyclicity. As a response, Petrovic and Thomassen (2006) in [4] and Yang (2009) in [6] gave some sufficient conditions for a strong hypertournament to be vertex-pancyclic. In this paper, we prove that, if is a strong -hypertournament on vertices, where , then is vertex-pancyclic. This extends the aforementioned results and Moon’s theorem for tournaments. Furthermore, our result is best possible in the sense that the bound is tight. [Copyright &y& Elsevier]

Abstract: Let be a graph with vertex set . A moplex of is both a clique and a module whose neighborhood is a minimal separator in or empty. A moplex ordering of is an ordered partition of for some integer into moplexes which are defined in the successive transitory elimination graphs, i.e., for , is a moplex of the graph induced by and induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on defines a moplex ordering of , which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques. [Copyright &y& Elsevier]