Search

Let r ≥ 2 and r be even. An r -hypergraph G on n vertices is called odd-colorable if there exists a map φ : [ n ] → [ r ] such that for any edge { j 1 , j 2 , … , j r } of G , we have φ ( j 1 ) + φ ( j 2 ) + ⋅ ⋯ ⋅ + φ ( j r ) ≡ r ∕ 2 ( mod r ) . In this paper, we first determine that, if r = 2 q ( 2 t + 1 ) and n ≥ 2 q ( 2 q − 1 ) r , then the maximum chromatic number in the class of the odd-colorable r -hypergraphs on n vertices is 2 q , which answers a question raised by V. Nikiforov recently in Nikiforov (2017). We also study some applications of the spectral symmetry of the odd-colorable r -hypergraphs given in the same paper by V. Nikiforov. We show that the Laplacian spectrum S p e c ( L ( G ) ) and the signless Laplacian spectrum S p e c ( Q ( G ) ) of an r -hypergraph G are equal if and only if r is even and G is odd-colorable. As an application of this result, we give an affirmative answer for the remaining unsolved case r ⁄ ≡ 0 ( m o d 4 ) of a question raised in Shao et al. (2015) about whether S p e c ( L ( G ) ) = S p e c ( Q ( G ) ) implies that L ( G ) and Q ( G ) have the same H-spectrum. [ABSTRACT FROM AUTHOR]

This is a survey or exposition of a particular collection of results and open problems involving snarks — simple “cubic” (3-valent) graphs for which, for nontrivial reasons, the edges cannot be 3-colored. The results and problems here are rooted in a series of papers by László Kászonyi that were published in the early 1970s. The problems posed in this survey paper can be tackled without too much specialized mathematical preparation, and in particular seem well suited for interested undergraduate mathematics students to pursue as independent research projects. This survey paper is intended to facilitate research on these problems. [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: The generalized Petersen graph is an undirected graph on vertices with and . Fiorini claimed to have determined the crossing numbers of and showed all the values of for up to 14, except 12 unknown values. Lovrečič Saražin proved . Richter and Salazar found a gap in Fiorini’s paper, which invalidated his principal results about , and gave the correct proof for . In this paper, we show the crossing numbers of all for up to 16. [Copyright &y& Elsevier]

Abstract: Neighborhoods and neighborhood sequences play important roles in several branches of pattern analysis. In earlier papers in only certain special (e.g. periodic or octagonal) sequences were investigated. In this paper we study neighborhood sequences which are either ultimately periodic or allow at every neighborhood to do nothing at no cost. We give finite procedures and descriptive theoretical criteria for certain important (e.g. metrical) properties of the sequences. Our results are valid for several types of classical neighborhood sequences and for generated distance functions (e.g. octagonal and chamfer distances) which are widely applied in digital image processing. We conclude the paper by showing how our results contribute to the theory of distance transformations. [Copyright &y& Elsevier]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

In this paper we continue studying the independent transversal domination number in a graph, i.e., the cardinality of a smallest dominating set which intersects each maximum independent set. As our main result, we prove two upper bounds on the independent transversal domination number in terms of the order and minimum degree of a graph. [ABSTRACT FROM AUTHOR]

The spectrum of a first order sentence is the set of all α such that G ( n , n − α ) does not obey zero–one law with respect to this sentence. In this paper, we prove that the minimal number of quantifier alternations of a first order sentence with infinite spectrum equals 3. We have also proved that the spectrum of a first-order sentence with quantifier depth 4 has no limit points except possibly the points 1 ∕ 2 and 3 ∕ 5 . [ABSTRACT FROM AUTHOR]

An edge-coloured connected graph G is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses k colours then G is called k -rainbow connected. The rainbow connection number of G , denoted by rc ( G ) , is the minimum k such that G is k -rainbow connected. Even the problem to decide whether rc ( G ) = 2 is NP-complete. It has been shown that if G is a connected graph of order n and size m with n − 2 2 + 2 ≤ m ≤ n − 1 2 , then 2 ≤ rc ( G ) ≤ 3 . In this paper we will present sufficient conditions for graphs G of this size to fulfil rc ( G ) = 2 depending on vertex degrees. [ABSTRACT FROM AUTHOR]

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: Wegner conjectured that for each planar graph with maximum degree at least 4, if , and if . Let be a planar graph without 4-cycles. In this paper, we discuss the -labelling of , and show that , where and are positive integers with . As a corollary, and . [Copyright &y& Elsevier]

Abstract: Let be positive integers. A -edge-colored graph is -e.c. or -existentially closed if for any disjoint sets of vertices with , there is a vertex not in such that all edges from this vertex to the set are colored by the -th color. In this paper, we give an explicit construction of a -e.c. graph of polynomial order. [Copyright &y& Elsevier]

Abstract: A sigraph is a graph in which each edge carries a value called its sign, denoted specially as . Given a sigraph , a new sigraph , called the common-edge sigraph of is that sigraph whose vertex-set is the set of pairs of adjacent edges in and two vertices of are adjacent if the corresponding pairs of adjacent edges of have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph carry + sign then is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, we characterize common-edge graph and common-edge sigraph and write an algorithm to obtain a corresponding common-edge root graph and common-edge root sigraph from a given common-edge graph and common-edge sigraph respectively. [Copyright &y& Elsevier]

Abstract: Let be a graph, a vertex labeling induces an edge labeling defined by for each . For each, define and . We call friendly if . The full friendly index set of is the set of all possible values of , where is friendly. In this paper, we study the full friendly index sets of some standard graphs such as the complete graph , the cycle , fans and and the Cartesian product of and i.e. . [Copyright &y& Elsevier]

Abstract: A nonbinary Ford sequence is a de Bruijn sequence generated by simple rules that determine the priorities of what symbols are to be tried first, given an initial word of size which is the order of the sequence being generated. This set of rules is generalized by the concept of a preference function of span , which gives the priorities of what symbols to appear after a substring of size is encountered. In this paper, we characterize preference functions that generate full de Bruijn sequences. More significantly, we establish that any preference function that generates a de Bruijn sequence of order also generates de Bruijn sequences of all orders higher than , thus making the Ford sequence no special case. Consequently, we define the preference function complexity of a de Bruijn sequence to be the least possible span of a preference function that generates this de Bruijn sequence. [Copyright &y& Elsevier]

Abstract: Given a graph , a vertex colouring of is -frugal if no colour appears more than times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind et al. (1997)  studied proper -frugal colourings and Yuster (1998)  studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study. [Copyright &y& Elsevier]

Abstract: An edge-coloring of a graph with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs. [Copyright &y& Elsevier]

Abstract: It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough. We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve. [Copyright &y& Elsevier]

Abstract: In this paper, we show that any incomplete hypercube with, at most, vertices can be embedded in pages for all . For the case , this result improves Fang and Lai’s result that any incomplete hypercube with, at most, vertices can be embedded in pages for all . Besides this, we show that the result can be further improved when is large — e.g., any incomplete hypercube with at most (respectively, ) vertices can be embedded in pages for all (respectively, ). [Copyright &y& Elsevier]

Abstract: Let denote the set of unicyclic graphs with a given diameter . In this paper, the unique unicyclic graph in with the maximum number of independent sets, is characterized. [Copyright &y& Elsevier]

Abstract: Given an acyclic digraph , the competition graph of is the graph with the same vertex set as where two distinct vertices and are adjacent in if and only if there is a vertex in such that and are arcs of . The competition number of a graph is the least number of isolated vertices that must be added to to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly holes, all of which are independent, is at most . This generalizes the result for given by Roberts, and the result for given by Cho and Kim. [Copyright &y& Elsevier]

Abstract: An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number of “do not know” symbols. We extend a result of Ehrenfeucht and Silberger which states that if a word can be written as a concatenation of nonempty prefixes of a word , then can be written as a unique concatenation of nonempty unbordered prefixes of . We study the properties of the longest unbordered prefix of a partial word, investigate the relationship between the minimal weak period of a partial word and the maximal length of its unbordered factors, and also investigate some of the properties of an unbordered partial word and how they relate to its critical factorizations (if any). [Copyright &y& Elsevier]

Abstract: Let be a graph. A function defined on the vertices of is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function is minimal if there does not exist a signed total dominating function , , for which for every . The weight of a signed total dominating function is the sum of its function values over all vertices of . The upper signed total domination number of is the maximum weight of a minimal signed total dominating function on . In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs. [Copyright &y& Elsevier]

Abstract: Let be a balanced bipartite graph of order . The path-cover number of a graph is the minimum number of vertex-disjoint paths that use up all the vertices of . is called a balanced set of if . In this paper, we will give some sufficient conditions for a balanced bipartite graph satisfying that for every balanced set , there is a bi-cycle of every length from up to through . [Copyright &y& Elsevier]

Abstract: A secret sharing scheme is a protocol by which a dealer distributes a secret among a set of participants in such a way that only qualified sets of them can reconstruct the value of the secret whereas any non-qualified subset of participants obtain no information at all about the value of the secret. Secret sharing schemes have always played a very important role for cryptographic applications and in the construction of higher level cryptographic primitives and protocols. In this paper we investigate the construction of efficient secret sharing schemes by using a technique called hypergraph decomposition, extending in a non-trivial way the previously studied graph decomposition techniques. A major advantage of hypergraph decomposition is that it applies to any access structure, rather than only structures representable as graphs. As a consequence, the application of this technique allows us to obtain secret sharing schemes for several classes of access structures (such as hyperpaths, hypercycles, hyperstars and acyclic hypergraphs) with improved efficiency over previous results. Specifically, for these access structures, we present secret sharing schemes that achieve optimal information rate. Moreover, with respect to the average information rate, our schemes improve on previously known ones. In the course of the formulation of the hypergraph decomposition technique, we also obtain an elementary characterization of the ideal access structures among the hyperstars, which is of independent interest. [Copyright &y& Elsevier]

Abstract: A binary linear code in with dimension and minimum distance is called an code. A design is a set of points together with a collection of -subsets of (called a block) such that every -subset of is contained in exactly blocks. A constant length code which corrects different numbers of errors in different code words is called a non-uniform error correcting code. Parity sectioned reduction of a linear code gives a non-uniform error correcting code. In this paper a new code, , is developed. The error correcting capability of this code is . It is shown that this code holds a design. Also the parity sectioned reduction code after deleting the same positions of each code word of this code holds a design for and . [Copyright &y& Elsevier]

Abstract: An offensive alliance in a graph is a set of vertices where for each vertex in its boundary the majority of vertices in ’s closed neighborhood are in . In the case of strong offensive alliance, strict majority is required. An alliance is called global if it affects every vertex in , that is, is a dominating set of . The global offensive alliance number is the minimum cardinality of a global offensive alliance in . An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number, , is the minimum cardinality of a global-connected offensive alliance in . In this paper we obtain several tight bounds on and in terms of several parameters of . The case of strong alliances is studied by analogy. [Copyright &y& Elsevier]

Abstract: The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self-stabilizing under the distributed daemon model. Although this result has been proven only recently, the correctness proof provided here is from a different point of view and is much more concise. We also show that Bruell et al.’s center-finding algorithm is actually self-stabilizing under the distributed daemon model. Finally, we compute the worst-case stabilization times of the two algorithms under the distributed daemon model. [Copyright &y& Elsevier]

Abstract: Given a simple polygon with two vertices and , the three-guard problem asks whether three guards can move from to such that the first and third guards are separately on two boundary chains of from to and the second guard is always kept to be visible from two other guards inside . It is a generalization of the well-known two-guard problem, in which two guards move on the boundary chains from to and are always kept to be mutually visible. In this paper, we introduce the concept of link-2-ray shots, which can be considered as ray shots under the notion of link-2-visibility. Then, we show a one-to-one correspondence between the structure of the restrictions placed on the motion of two guards and the one placed on the motion of three guards, and generalize the solution for the two-guard problem to that for the three-guard problem. We can decide whether there exists a solution for the three-guard problem in time, and if so generate a walk in time, where denotes the number of vertices of and the size of the optimal walk. This improves upon the previous time bounds and , respectively. Moreover, our results can be used to solve other more sophisticated geometric problems. [Copyright &y& Elsevier]

Abstract: The Padmakar–Ivan (PI) index of a graph G is the sum over all edges of G of the number of edges which are not equidistant from and . In this paper, the notion of vertex PI index of a graph is introduced. We apply this notion to compute an exact expression for the PI index of Cartesian product of graphs. This extends a result by Klavzar [On the PI index: PI-partitions and Cartesian product graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 573–586] for bipartite graphs. Some important properties of vertex PI index are also investigated. [Copyright &y& Elsevier]

Abstract: For the earliest arrival flow problem one is given a network with capacities and transit times on its arcs , together with a source and a sink vertex . The objective is to send flow from s to t that moves through the network over time, such that for each time the maximum possible amount of flow up to this time reaches t. If, for each , this flow is a maximum flow for time horizon , then it is called earliest arrival flow. In practical applications a higher congestion of an arc in the network often implies a considerable increase in transit time. Therefore, in this paper we study the earliest arrival problem for the case that the transit time of each arc in the network at each time depends on the flow on this particular arc at that time . For constant transit times it has been shown by Gale that earliest arrival flows exist for any network. We give examples, showing that this is no longer true for flow-dependent transit times. For that reason we define a relaxed version of this problem where the objective is to find flows that are almost earliest arrival flows. In particular, we are interested in flows that, for each , need only -times longer to send the maximum flow to the sink. We give both constant lower and upper bounds on ; furthermore, we present a constant factor approximation algorithm for this problem. [Copyright &y& Elsevier]

Abstract: Mobile agents are software abstractions that can migrate across the links of a network. They naturally extend the object oriented program style and nicely correspond to agents as examined in game theory. In this paper, we introduce a simple, robust, and efficient randomized broadcast protocol within this mobile agent programming paradigm. We show that by using this scheme, broadcasting enquiries in a random graph of certain density steps, where denotes the number of nodes in the graph. Then, we consider bounded degree graphs and prove that we are able to distribute an information among all nodes in steps, where denotes the diameter of the graph. We also show that, in contrast to traditional randomized broadcasting (TRB), graphs exist in which agent-based randomized broadcasting requires steps. On the other hand, some graphs which require steps to spread the information in the traditional broadcast model, allow very fast agent-based broadcasting. It should be noted that the previously mentioned results are guaranteed with probability . [Copyright &y& Elsevier]

Abstract: This paper discusses a kind of bent functions that have some symmetric properties about some variables. Section 2 mainly discusses the bent functions symmetric about some two variables and gives the necessary and sufficient condition for these functions. Section 3 gives algebraic expressions of some bent functions. [Copyright &y& Elsevier]

Abstract: In this paper a novel method for indexing views of 3D objects is presented. The topological properties of the regions of views of an object or of a set of objects are used to define an index based on region connection calculus and oriented matroid theory. Both are formalisms for qualitative spatial representation and reasoning and are complementary in the sense that, whereas region connection calculus characterize connectivity of couples of connected regions of views, oriented matroids encode relative position of disjoint regions of views and give local and global topological information about their spatial distribution. This indexing technique has been applied to hypothesis generation from a single view to reduce the number of candidates in 3D object recognition processes. [Copyright &y& Elsevier]

In this paper, we present a repair-based linear-time algorithm to solve a version of the Sports League Scheduling Problem (SLSP) where the number T of teams is such that (T-1) mod 3≠0. Starting with a conflicting schedule with particular properties, the algorithm removes iteratively the conflicts by exchanging matches. The properties of the initial schedule make it possible to take the optimal exchange at each iteration, leading to a linear-time algorithm. This algorithm can find thus valid schedules for several thousands of teams in less than 1 min. It is still an open question whether the SLSP can be solved efficiently when (T-1) mod 3=0. [Copyright &y& Elsevier]

Let ΓnA denote the abstract simplicial complex whose elements are dissections of a convex (n+2)-gon. Lee proved that ΓnA is the boundary complex of a convex polytope, now known as the associahedron. Simion constructed a type-B associahedron whose faces correspond to centrally symmetric dissections of a (2n+2)-gon. In this paper, we define a partial order on the set of centrally symmetric triangulations whose Hasse diagram is the 1-skeleton of the simple B-associahedron and explore properties of this poset, including encodings, self-duality, and chain length. We also establish lattice failure and goodness. [Copyright &y& Elsevier]

Abstract: Given a signed digraph on a given digraph called the underlying digraph of , its signed line digraph is a signed digraph defined on the line digraph of by defining an arc in it to be negative if and only if both the arcs and in are negative and oriented in the same direction through their common vertex. In this paper, we define a given signed digraph to be a signed line digraph if there exists a signed digraph such that (read as “ is isomorphic to ”). We derive three structural characterizations of signed line digraphs, extending the well known characterization of line digraphs due to Hemminger (1972) [10]. [Copyright &y& Elsevier]

Abstract: A graph is domination dot-critical, or just dot-critical, if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. In this paper, we study an open question concerning of the diameter of a domination dot-critical graph . [Copyright &y& Elsevier]

Abstract: Let be a graph of order and denote the signed edge domination number of . In [B. Xu, Two classes of edge domination in graphs, Discrete Appl. Math. 154 (2006) 1541–1546] it was proved that for any graph of order , . But the method given in the proof is not correct. In this paper we give an example for which the method of proof given in [1] does not work. [Copyright &y& Elsevier]