Search

Given a set system (also well-known as a hypergraph) H = {U, X}, where U is a set of elements and X is a set of subsets of U, an exact hitting set S is a subset of U such that each subset in X contains exactly one element in S. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as Exactly Hittable Interval Graphs (EHIG). We present a forbidden structure characterization for EHIG. We also show that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs in polynomial time to recognize graphs belonging to the class of EHIG. [ABSTRACT FROM AUTHOR]

An edge-colored graph is rainbow if no two edges of the graph have the same color. An edge-colored graph Gc is called properly colored if every two adjacent edges of Gc receive distinct colors in Gc. A strongly edge-colored graph is a proper edge-colored graph such that every path of length 3 is rainbow. We call an edge-colored graph Gc rainbow vertex pair-pancyclic if any two vertices in Gc are contained in a rainbow cycle of length ℓ for each ℓ with 3 ≤ ℓ ≤ n. In this paper, we show that every strongly edge-colored graph Gc of order n with minimum degree δ ≤ 2n/3 + 1 is rainbow vertex pair-pancyclicity. [ABSTRACT FROM AUTHOR]

The following problem has been known since the 80's. Let Γ be an Abelian group of order m (denoted |Γ| = m), and let t and mi, 1 ≤ i ≤ t, be positive integers such ∑i=1t mi = m -- 1. Determine when Γ* = Γ \ {0}, the set of non-zero elements of Γ, can be partitioned into disjoint subsets Si, 1 ≤ i ≤ t, such that |Si| = mi and ... s = 0 for every i 2 [1; t]. It is easy to check that mi ≥ 2 (for every i ∈ [1, t]) and |I(Γ)| ≠= 1 are necessary conditions for the existence of such partitions, where I(Γ) is the set of involutions of Γ. It was proved that the condition mi ≥ 2 is sufficient if and only if |I(Γ)} ∈ {0, 3} (see Zeng, (2015)). For other groups (i.e., for which |I(Γ)} ≠ 3 and |I(Γ)| > 1), only the case of any group Γ with Γ ≅ = (ℤ2)n for some positive integer n has been analyzed completely so far, and it was shown independently by several authors that mi ≥ 3 is sufficient in this case. Moreover, recently Cichacz and Tuza (2021) proved that, if |Γ| is large enough and |I(Γ)| > 1, then mi ≥ 4 is sufficient. In this paper we generalize this result for every Abelian group of order 2n. Namely, we show that the condition mi ≥ 3 is sufficient for Γ such that |I(Γ)} > 1 and |Γ| = 2n, for every positive integer n. We also present some applications of this result to graph magic- and anti-magic-type labelings. [ABSTRACT FROM AUTHOR]

This paper considers the following three Roman domination graph invariants on Kneser graphs: Roman domination, total Roman domination, and signed Roman domination. For Kneser graph Kn,k, we present exact values for Roman domination number γR(Kn,k) and total Roman domination number γR(Kn,k) proving that for n ≥ k(k + 1), γR(Kn,k) = γR(Kn,k) = 2(k + 1). For signed Roman domination number γR(Kn,k), the new lower and upper bounds for Kn,2 are provided: we prove that for n ≥ 12, the lower bound is equal to 2, while the upper bound depends on the parity of n and is equal to 3 if n is odd, and equal to 5 if n is even. For graphs of smaller dimensions, exact values are found by applying exact methods from literature. [ABSTRACT FROM AUTHOR]

We consider the constrained graph alignment problem which has applications in biological network analysis. Given two input graphs G1 = (V1; E1), G2 = (V2, E2), two vertices u1, v1 of G1 paired respectively to two vertices u2, v2 of G2 induce an edge conservation if u1, v1 and u2, v2 are adjacent in their respective graphs. The goal is to provide a one-to-one mapping between some vertices of the input graphs in order to maximize edge conservation. However the allowed mappings are restricted since each vertex from V1 (resp. V2) is allowed to be mapped to at most m1 (resp. m²) specified vertices in V2 (resp. V1). Most of the results in this paper deal with the case m² = 1 which attracted most attention in the related literature. We formulate the problem as a maximum independent set problem in a related conflict graph and investigate structural properties of this graph in terms of forbidden subgraphs. We are interested, in particular, in excluding certain wheels, fans, cliques or claws (all terms are defined in the paper), which in turn corresponds to excluding certain cycles, paths, cliques or independent sets in the neighborhood of each vertex. Then, we investigate algorithmic consequences of some of these properties, which illustrates the potential of this approach and raises new horizons for further works. In particular this approach allows us to reinterpret a known polynomial case in terms of conflict graph and to improve known approximation and fixed-parameter tractability results through efficiently solving the maximum independent set problem in conflict graphs. Some of our new approximation results involve approximation ratios that are functions of the optimal value, in particular its square root; this kind of results cannot be achieved for maximum independent set in general graphs. [ABSTRACT FROM AUTHOR]

The average distance of a vertex v of a connected graph G is the arithmetic mean of the distances from v to all other vertices of G. The proximity π(G) and the remoteness ρ(G) of G are the minimum and the maximum of the average distances of the vertices of G, respectively. In this paper, we give upper bounds on the remoteness and proximity for graphs of given order, minimum degree and maximum degree. Our bounds are sharp apart from an additive constant. [ABSTRACT FROM AUTHOR]

Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. In particular, the layered treewidth of a graph G is the minimum integer k such that G has a tree-decomposition and a layering such that each bag has at most k vertices in each layer. The row treewidth of G is the minimum integer k such that G is isomorphic to a subgraph of H - P for some graph H of treewidth at most k and for some path P. It follows from the definitions that the layered treewidth of a graph is at most its row treewidth plus 1. Moreover, a minor-closed class has bounded layered treewidth if and only if it has bounded row treewidth. However, it has been open whether row treewidth is bounded by a function of layered treewidth. This paper answers this question in the negative. In particular, for every integer k we describe a graph with layered treewidth 1 and row treewidth k. We also prove an analogous result for layered pathwidth and row pathwidth. [ABSTRACT FROM AUTHOR]

Given a graph G and an integer k, it is an NP-complete problem to decide whether G has a dominating set of size at most k. In this paper we study this problem for the Knödel Graph on n vertices using elementary number theory techniques. In particular, we show an explicit upper bound for the domination number of the Knödel Graph on n vertices any time that we can find a prime number p dividing n for which 2 is a primitive root. [ABSTRACT FROM AUTHOR]

The determining number of a graph G = (V,E) is the minimum cardinality of a set S ⊑ V such that pointwise stabilizer of S under the action of Aut(G) is trivial. In this paper, we provide some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we provide the exact value of the determining number for some subfamilies of Kneser graphs. [ABSTRACT FROM AUTHOR]

Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i. e. admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. In this paper we study graphs of bounded degree that are far from being Hamiltonian, where a graph G on n vertices is far from being Hamiltonian, if modifying a constant fraction of n edges is necessary to make G Hamiltonian. We give an explicit deterministic construction of a class of graphs of bounded degree that are locally Hamiltonian, but (globally) far from being Hamiltonian. Here, locally Hamiltonian means that every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph. More precisely, we obtain graphs which differ in (n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of o(n) vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with two-sided error) requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010). This is proved via a randomised construction of hard instances. In contrast, our construction is deterministic. So far only very few deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties that are testable in the bounded-degree model. [ABSTRACT FROM AUTHOR]

Let k and n be integers such that 1 ≤ k ≤ n 1, and let G be a simple graph of order n. The k-token graph Fk(G) of G is the graph whose vertices are the k-subsets of V (G), where two vertices are adjacent in Fk(G) whenever their symmetric difference is an edge of G. In this paper we show that if G is a tree, then the connectivity of Fk(G) is equal to the minimum degree of Fk(G). [ABSTRACT FROM AUTHOR]

An equitable partition into branchings in a digraph is a partition of the arc set into branchings such that the sizes of any two branchings differ at most by one. For a digraph whose arc set can be partitioned into k branchings, there always exists an equitable partition into k branchings. In this paper, we present two extensions of equitable partitions into branchings in digraphs: those into matching forests in mixed graphs; and into b-branchings in digraphs. For matching forests, Király and Yokoi (2022) considered a tricriteria equitability based on the sizes of the matching forest, and the matching and branching therein. In contrast to this, we introduce a single-criterion equitability based on the number of covered vertices, which is plausible in the light of the delta-matroid structure of matching forests. While the existence of this equitable partition can be derived from a lemma in Király and Yokoi, we present its direct and simpler proof. For b-branchings, we define an equitability notion based on the size of the b-branching and the indegrees of all vertices, and prove that an equitable partition always exists. We then derive the integer decomposition property of the associated polytopes. [ABSTRACT FROM AUTHOR]

Let H = (V, F) be a simple hypergraph without loops. H is called linear if |f ∩g| ≤ 1 for any f, g ∈ F with f 6= g. The 2-section of H, denoted by [H]2, is a graph with V ([H]2) = V and for any u, v ∈ V ([H]2), uv ∈ E([H]2) if and only if there is f ∈ F such that u, v ∈ f. The treewidth of a graph is an important invariant in structural and algorithmic graph theory. In this paper, we consider the treewidth of the 2-section of a linear hypergraph. We will use the minimum degree, maximum degree, anti-rank and average rank of a linear hypergraph to determine the upper and lower bounds of the treewidth of its 2-section. Since for any graph G, there is a linear hypergraph H such that [H]2 ∼= G, we provide a method to estimate the bound of treewidth of graph by the parameters of the hypergraph. [ABSTRACT FROM AUTHOR]

A graph G is weighted–k–list–antimagic if for any vertex weighting ω: V (G) → R and any list assignment L: E(G) → 2R with |L(e)| ≥ |E(G)| + k there exists an edge labeling f such that f(e) ∈ L(e) for all e ∈ E(G), labels of edges are pairwise distinct, and the sum of the labels on edges incident to a vertex plus the weight of that vertex is distinct from the sum at every other vertex. In this paper we prove that every graph on n vertices having no K1 or K2 component is weighted–[ 4n/3 ] –list–antimagic. [ABSTRACT FROM AUTHOR]

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on n vertices with an O(n4) time delay. In this paper, we improve their algorithm and achieve O(n3 log n) time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all n up to 15. [ABSTRACT FROM AUTHOR]

In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function. Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In particular, it is useful to find discretization orders that minimize an indicator of the size of the search tree. Our stepwise linear cost function generalizes this situation and allows to discriminate the vertices into three categories depending on the number of adjacent predecessors of each vertex in the order and on two parameters K and U. We provide a complete study of NP-completeness for fixed values of K and U. Our main result is that the problem is NP-complete in general for all values of K and U such that U ≥K + 1 and U ≥2. A consequence of this result is that the minimization of vertices with exactly K adjacent predecessors in a discretization order is also NP-complete. [ABSTRACT FROM AUTHOR]

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as 2×n, 3×n, 4×n, and 5×n grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within O(m+n) of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by mn6+O(m+n). We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by mn7+O(m+n). While this does not improve upon a recently announced bound of ⌈m3⌉⌈n3⌉+O(mn--√) [Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179. [ABSTRACT FROM AUTHOR]

It is commonly believed that real networks are scale-free and the fraction of nodes P(k) with degree k satisfies the power-law P(k) / k-γ for k > kmin > 0. Preferential attachment is the mechanism that has been considered responsible for such organization of these networks. In many real networks, degree distribution before the kmin varies very slowly to the extent of being uniform as compared to the degree distribution for k > kmin. In this paper, we propose a model that describes this particular degree distribution for the whole range of k > 0. We adopt a two step approach. In the first step, at every time stamp we add a new node to the network and attach it to an existing node using preferential attachment method. In the second step, we add edges between existing pairs of nodes with the node selection based on the uniform probability distribution. Our approach generates weakly scale-free networks that closely follow the degree distribution of real-world networks. We perform a comprehensive mathematical analysis of the model in the discrete domain and compare the degree distribution generated by this model with that of real-world networks. [ABSTRACT FROM AUTHOR]

Define a sequence of elements from a partially ordered set to be heapable if it can be successively inserted as the leaves of a binary tree, not necessarily complete, such that children nodes are always greater or equal than parent nodes. This is a natural binary analog of the notion of a chain in a poset and an easy extension of a definition for integers due to Byers et al. (2011). A set of elements is called heapable if some permutation of its elements is. We investigate the partitioning of sequences from a poset into a minimal number of heapable subsequences. We give an extension of Fulkerson's proof of Dilworth's theorem to decomposition into heapable subsequences which yields as a byproduct a flow-based algorithm for computing such a minimal decomposition. On the other hand, for sets and sequences of intervals and for trapezoid partial orders we prove that such minimal decompositions can be computed via simple greedy-type algorithms. Second, while the complexity of computing a maximal heapable subsequence of integers is still open, we show that this problem has a polynomial time algorithm for sequences of intervals. The paper concludes with a couple of open problems related to the analog of the Ulam-Hammersley problem for sets and sequences of random intervals. [ABSTRACT FROM AUTHOR]

The enumeration of inversion sequences avoiding a single pattern was initiated by Corteel, Martinez, Savage and Weselcouch, and Mansour and Shattuck, independently. Their work has sparked various investigations of generalized patterns in inversion sequences, including patterns of relation triples by Martinez and Savage, consecutive patterns by Auli and Elizalde, and vincular patterns by Lin and Yan. In this paper, we carried out the systematic study of inversion sequences avoiding two patterns of length 3. Our enumerative results establish further connections to the OEIS sequences and some classical combinatorial objects, such as restricted permutations, weighted ordered trees and set partitions. Since patterns of relation triples are some special multiple patterns of length 3, our results complement the work by Martinez and Savage. In particular, one of their conjectures regarding the enumeration of (021, 120)- avoiding inversion sequences is solved. [ABSTRACT FROM AUTHOR]

Let Sa;b denote the sequence of leading digits of an in base b. It is well known that if a is not a rational power of b, then the sequence Sa;b satisfies Benford's Law; that is, digit d occurs in Sa;b with frequency logb(1 + 1/d), for d = 1; 2; : : : ; b-1. In this paper, we investigate the complexity of such sequences. We focus mainly on the block complexity, pa;b(n), defined as the number of distinct blocks of length n appearing in Sa;b. In our main result we determine pa;b(n) for all squarefree bases b ≥ 5 and all rational numbers a > 0 that are not integral powers of b. In particular, we show that, for all such pairs (a; b), the complexity function pa;b(n) is an affine function, i.e., of the form pa;b(n) = ca;bn+da;b for all n ≥ 1, with coefficients ca;b ≥ 1 and da;b ≥ 0, given explicitly in terms of a and b. We also show that the requirement that b be squarefree cannot be dropped: If b is not squarefree, then there exist integers a with 1 < a < b for which pa;b(n) is not of the above form. We use this result to obtain sharp upper and lower bounds for pa;b(n) and to determine the asymptotic behavior of this function as b ! 1 through squarefree values. We also consider the question which affine functions p(n) = cn + d arise as the complexity function pa;b(n) of some leading digit sequence Sa;b. We conclude with a discussion of other complexity measures for the sequences Sa;b and some open problems. [ABSTRACT FROM AUTHOR]

Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph G is a graph that admits a representation where its vertices correspond to paths in a grid Q, such that two vertices of G are adjacent if and only if their corresponding paths in Q have a common edge. If the paths in the representation have at most k bends, we say that it is a Bk-EPG representation. A collection C of sets satisfies the Helly property when every sub-collection of C that is pairwise intersecting has at least one common element. In this paper, we show that given a graph G and an integer k, the problem of determining whether G admits a Bk-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-Bk-EPG representation, is in NP, for every k bounded by a polynomial function of jV (G)j. Moreover, we show that the problem of recognizing Helly-B1-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs. [ABSTRACT FROM AUTHOR]

Let P be a set of n≥4 points in general position in the plane. Consider all the closed straight line segments with both endpoints in P. Suppose that these segments are colored with the rule that disjoint segments receive different colors. In this paper we show that if P is the point configuration known as the double chain, with k points in the upper convex chain and l≥k points in the lower convex chain, then k+l-√2l+1/4-1/2˩ colors are needed and that this number is sufficient. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to study a statistic that is used to compare the similarity between two strings, which is first introduced by Michael Steele in 1982. It was proposed as an alternative to the length of the longest common subsequences, for which the variance problem is still open. Our results include moment asymptotics and distributional asymptotics for Steele's statistic and a variation of it in random words. [ABSTRACT FROM AUTHOR]

Let G = (X, Y ;E) be a bipartite graph, where X and Y are color classes and E is the set of edges of G. Lov´asz and Plummer asked whether one can decide in polynomial time that a given bipartite graph G = (X, Y ;E) admits a 1-anti-factor, that is subset F of E such that dF (v) = 1 for all v ∈ X and dF (v) 6= 1 for all v ∈ Y . Cornuéjols answered this question in the affirmative. Yu and Liu asked whether, for a given integer k ≥ 3, every k-regular bipartite graph contains a 1-anti-factor. This paper answers this question in the affirmative. [ABSTRACT FROM AUTHOR]

Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially the set S together with all its neighbors. Then iteratively, whenever some monitored vertex v has a single neighbor u not yet monitored, u gets monitored. A set S is said to be a power dominating set of the graph G if all vertices of G eventually are monitored. The power domination number of a graph is the minimum size of a power dominating set. In this paper, we prove that any maximal planar graph of order n ≥ 6 admits a power dominating set of size at most n-2/4. [ABSTRACT FROM AUTHOR]

The family of generalised Petersen graphs G(n, k), introduced by Coxeter et al. [4] and named byWatkins (1969), is a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. The Kronecker cover KC(G) of a simple undirected graph G is a special type of bipartite covering graph of G, isomorphic to the direct (tensor) product of G and K2. We characterize all generalised Petersen graphs that are Kronecker covers, and describe the structure of their respective quotients. We observe that some of such quotients are again generalised Petersen graphs, and describe all such pairs. The results of this paper have been presented at EUROCOMB 2019 and an extended abstract has been published elsewhere. [ABSTRACT FROM AUTHOR]

Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously NP-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of length 1). On the other hand, a famous result of Lovász states that deciding whether a graph admits an ear decomposition with all ears of odd length can be done in polynomial time. In this paper, we study the complexity of deciding whether a graph admits an ear decomposition with prescribed ear lengths. We prove that deciding whether a graph admits an ear decomposition with all ears of length at most ℓ is polynomial-time solvable for all fixed positive integer ℓ. On the other hand, deciding whether a graph admits an ear decomposition without ears of length in F is NP-complete for any finite set F of positive integers. We also prove that, for any k ≥ 2, deciding whether a graph admits an ear decomposition with all ears of length 0 mod k is NP-complete. We also consider the directed analogue to ear decomposition, which we call handle decomposition, and prove analogous results : deciding whether a digraph admits a handle decomposition with all handles of length at most ℓ is polynomial-time solvable for all positive integer ℓ; deciding whether a digraph admits a handle decomposition without handles of length in F is NP-complete for any finite set F of positive integers (and minimizing the number of handles of length in F is not approximable up to n(1 - ∈)); for any k ≥ 2, deciding whether a digraph admits a handle decomposition with all handles of length 0 mod k is NP-complete. Also, in contrast with the result of Lovász, we prove that deciding whether a digraph admits a handle decomposition with all handles of odd length is NP-complete. Finally, we conjecture that, for every set A of integers, deciding whether a digraph has a handle decomposition with all handles of length in A is NP-complete, unless there exists h ∈ ℕ such that A = {1, &#8943, h}. [ABSTRACT FROM AUTHOR]

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu (2017) recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number of G is the minimum number of vertices and edges whose deletion leaves the resulting graph without a fractional perfect matching. In this paper, we obtain the fractional matching preclusion number and the fractional strong matching preclusion number for generalized augmented cubes. In addition, all the optimal fractional strong matching preclusion sets of these graphs are categorized. [ABSTRACT FROM AUTHOR]

Edge-connectivity is a classic measure for reliability of a network in the presence of edge failures. k-restricted edgeconnectivity is one of the refined indicators for fault tolerance of large networks. Matching preclusion and conditional matching preclusion are two important measures for the robustness of networks in edge fault scenario. In this paper, we show that the DCell network Dk, n is super-γ for k ≥ 2 and n ≥2, super-γ2 for k ≥ 3 and n ≥ 2, or k = 2 and n = 2, and super-γ3 for k ≥ 4 and n ≥ 3. Moreover, as an application of k-restricted edge-connectivity, we study the matching preclusion number and conditional matching preclusion number, and characterize the corresponding optimal solutions of Dk,n. In particular, we have shown that D1;n is isomorphic to the (n, k)-star graph Sn+1,2 for n ≥ 2. [ABSTRACT FROM AUTHOR]

In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, where we have shown, in particular, that there are no such graphs with more than 5 colors. Using some recent results, with a help of computer, we settle all the cases that was left open in the previous paper. [ABSTRACT FROM AUTHOR]

Let G be a graph and S be a subset of Z. A vertex-coloring S-edge-weighting of G is an assignment of weights by the elements of S to each edge of G so that adjacent vertices have different sums of incident edges weights. It was proved that every 3-connected bipartite graph admits a vertex-coloring S-edge-weighting for S = {1, 2} (H. Lu, Q. Yu and C. Zhang, Vertex-coloring 2-edge-weighting of graphs, European J. Combin., 32 (2011), 22-27). In this paper, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring S-edge- weighting for S ∈ {{0, 1}, {1, 2}}. These bounds we obtain are tight, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring S-edge-weightings for S ∈ {{0, 1}, {1, 2}}. [ABSTRACT FROM AUTHOR]

A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X - {v}) υ {u} is again a dominating set of G. The secure domination number of G is the cardinality of a smallest secure dominating set of G. A graph G is p-stable if the largest arbitrary subset of edges whose removal from G does not increase the secure domination number of the resulting graph, has cardinality p. In this paper we study the problem of computing p-stable graphs for all admissible values of p and determine the exact values of p for which members of various infinite classes of graphs are p-stable. We also consider the problem of determining analytically the largest value ωn of p for which a graph of order n can be p-stable. We conjecture that ωn = n - 2 and motivate this conjecture. [ABSTRACT FROM AUTHOR]

A κ-edge-weighting of a graph G is a function w : E(G) → {1, . . ., κ}. An edge-weighting naturally induces a vertex coloring c, where for every vertex ν ∈ V (G), c(ν) = Σe~v w(e). If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring κ-edge-weighting (VC κ-EW). Karoński et al. (J. Combin. Theory Ser. B, 91 (2004) 151-157) conjectured that every graph admits a VC 3-EW. This conjecture is known as the 1-2-3-conjecture. In this paper, first, we study the vertex-coloring edge-weighting of the Cartesian product of graphs. We prove that if the 1-2-3-conjecture holds for two graphs G and H, then it also holds for G〉H. Also we prove that the Cartesian product of connected bipartite graphs admits a VC 2-EW. Moreover, we present several sufficient conditions for a graph to admit a VC 2-EW. Finally, we explore some bipartite graphs which do not admit a VC 2-EW. [ABSTRACT FROM AUTHOR]

The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L(p, q)-labeling, channel assignment and T-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We ask for a labeling of vertices of the input graph with natural numbers, in which every vertex gets a label from its list of permitted labels and the difference of labels of the endpoints of each edge does not belong to the set of forbidden differences of this edge. In this paper we present an exact algorithm solving this problem, running in time O* ((τ + 2)n), where t is the maximum forbidden difference over all edges of the input graph and n is the number of its vertices. Moreover, we show how to improve this bound if the input graph has some special structure, e.g. a bounded maximum degree, no big induced stars or a perfect matching. [ABSTRACT FROM AUTHOR]

The oriented diameter of a bridgeless graph G is min{diam(H) | H is a strang orientation of G}. A path in an edge-colored graph G, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer number k for which there exists a k-edge-coloring of G such that every two distinct vertices of G are connected by a rainbow path. In this paper, we obtain upper bounds for the oriented diameter and the rainbow connection number of a graph in terms of rad(G) and η(G), where rad(G) is the radius of G and η (G) is the smallest integer number such that every edge of G is contained in a cycle of length at most η (G). We also obtain constant bounds of the oriented diameter and the rainbow connection number for a (bipartite) graph G in terms of the minimum degree of G. [ABSTRACT FROM AUTHOR]

In their 2009 paper, Corneil et al. design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to the LBFS structure theory established mainly by Corneil et al., we are able to present a 4-sweep LBFS algorithm which determines whether or not the input graph is a unit interval graph or an interval graph. Like the algorithm of Corneil et al., our algorithm does not involve any complicated data structure and can be executed in linear time. [ABSTRACT FROM AUTHOR]

As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition is an NP-complete problem for general graphs, and is polynomial time solvable for several classes of graphs. In this paper, we investigate graphs that admit a unique such partition and call them uniquely monopolar-partitionable graphs. By employing a tree trimming technique, we obtain a characterization of uniquely monopolar-partitionable block graphs. Our characterization implies a polynomial time algorithm for determining whether a block graph is uniquely monopolar-partitionable. [ABSTRACT FROM AUTHOR]

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the end-points of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in Zp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs. [ABSTRACT FROM AUTHOR]

Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is Gm+2. Brandstadt et al. in [Andreas Brandstadt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Mathematics, 177(1-3):9-16, 1997.] showed that if Gm is k-chordal, then so is Gm+2. Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. The m-th bipartite power G[m] of a bipartite graph G is the bipartite graph obtained from G by adding edges (u, v) where dG (u, v) is odd and less than or equal to m. Note that G[m] = G[m + 1] for each odd m. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G[m], where k, m are positive integers with k ≥ 4. [ABSTRACT FROM AUTHOR]

Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out some promising research directions. We also sketch the general framework of a unified approach to show the NP-hardness of some problems in subgrids. [ABSTRACT FROM AUTHOR]

We draw the r - dimensional butterfly network with 1/4r+O(r2r) crossings which improves the previous estimate given by Cimikowski (1996). We also give a lower bound which matches the upper bound obtained in this paper. [ABSTRACT FROM AUTHOR]

For a brick apart from a few small graphs, Lovász (1987) proposed a conjecture on the existence of an edge whose deletion results in a graph with only one brick in its tight cut decomposition. Carvalho, Lucchesi, and Murty (2002) confirmed this conjecture by showing the existence of such two edges. This paper generalizes the result obtained by Carvalho et al. to the case of irreducible near-brick, where a graph is irreducible if it contains no induced odd path of length 3 or more. Meanwhile, a lower bound on the number of removable edges of matching-covered bipartite graphs is presented. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c(r-1|V(H)|-1 minimum degree of a pair of vertices at least c(r-2|V(H)|-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain the first optimal dichotomy results for 2-colorings of r-uniform hypergraphs. For each problem and each r ≥ 3, we determine a threshold value depending on r such that the problem is NP-complete for c below the threshold, while for c strictly above the threshold it is polynomial. We provide an algorithm constructing the coloring with time complexity O(nC), for some C = C(c, r) > 0. This algorithm becomes more efficient in cases r = 3,4, 5 due to known Turán numbers of the triangle and the Fano plane. In addition, we determine the computational complexity of strong coloring of 3-uniform hypergraphs H with minimum vertex degree at least c(2|V(H)|-1, for some c, leaving a gap for k ≥ 5, which vanishes as k →∞. [ABSTRACT FROM AUTHOR]

A cyclic q-partition of a hypergraph (V, E) is a partition of the edge set E of the form {F,Fθ,Fθ²,..., Feθq-1} for some permutation θ of the vertex set V. Let Vn = {1,2,...,n}. For a positive integer k, (kVn) denotes the set of all k-subsets of Vn. For a nonempty subset K of Vn-1, we let Kn(K) denote the hypergraph (Vn, UkεK(kVn)). In this paper, we find a necessary and sufficient condition on n, q and k for the existence of a cyclic q-partition of Kn(Vk). In particular, we prove that if p is prime then there is a cyclic pα-partition of Kn(Vk) if and only if pα+β divides n, where β = [logpk). As an application of this result, we obtain two sufficient conditions on n1, n2, ..., nt, k, α and a prime p for the existence of a cyclic pα-partition of the complete t-partite k-uniform hypergraph Kn1,n2,...,nt(k). [ABSTRACT FROM AUTHOR]

Let f(n, k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that (1/2) n²/k-1 - n/2 ≤ 2 n(n-2)/k-2. For the case when k = n, we show that 2 ≤ f(n, n) ≤ 3. For the case when k = n and G is a geometric graph on a set of points in convex position, we completely solve the problem and prove that at least three edges must be removed. [ABSTRACT FROM AUTHOR]

A b-coloring of a graph G by k colors is a proper vertex coloring such that each color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k - 1 color classes. The b-chromatic number Χb (G) is the maximum integer k for which G has a b-coloring by k colors. Let Cnr be the rth power of a cycle of order n. In 2003, Effantin and Kheddouci established the b-chromatic number Χb (Cnr) for all values of n and r, except for 2r + 3 ≤ n ≤ 3r. For the missing cases they presented the lower bound L := min {n - r - 1, r + 1 + ⌊ n-r-1/3⌋} and conjectured that Χb (Cnr) > L. In this paper, we determine the exact value on Χb (Cn4) for the missing cases. It turns out that Χb (Cnr) > L for 2r + 3 ≤ n ≤ 2r + 3 + r-6/4 . [ABSTRACT FROM AUTHOR]

A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle of length 4 contains a vertex that is dominated by the vertex of the cycle that is not adjacent to it. In this paper we show that the class of hereditary biclique-Helly graphs is formed precisely by those C4-dominated graphs that contain no triangles and no induced cycles of length either 5 or 6. Using this characterization, we develop an algorithm for recognizing hereditary biclique-Helly graphs in O(n² + αm) time and O(n+m) space. (Here n, m, and α = O(m1/2) are the number of vertices and edges, and the arboricity of the graph, respectively.) As a subprocedure, we show how to recognize those C4-dominated graphs that contain no triangles in O(αm) time and O(n + m) space. Finally, we show how to enumerate all the maximal bicliques of a C4-dominated graph with no triangles in O(n² + am) time and O(αm) space. [ABSTRACT FROM AUTHOR]

A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G is the minimum cardinality of a determining set of G. This paper studies the determining number of Kneser graphs. First, we compute the determining number of a wide range of Kneser graphs, concretely Kn:k with n ≥ k(k + 1)/2 + 1. In the language of group theory, these computations provide exact values for the base size of the symmetric group Sn acting on the k-subsets of {1, …, n}. Then, we establish for which Kneser graphs Kn:k the determining number is equal to n - k, answering a question posed by Boutin. Finally, we find all Kneser graphs with fixed determining number 5, extending the study developed by Boutin for determining number 2, 3 or 4. [ABSTRACT FROM AUTHOR]

A Krausz (k,m)-partition of a graph G is a decomposition of G into cliques, such that any vertex belongs to at most k cliques and any two cliques have at mostmvertices in common. Them-Krausz dimension kdim m (G) of the graph G is the minimum number k such that G has a Krausz (k,m)-partition. In particular, 1-Krausz dimension or simply Krausz dimension kdim(G) is a well-known graph-theoretical parameter. In this paper we prove that the problem "kdim(G) ≤ 3" is polynomially solvable for chordal graphs, thus partially solving the open problem of P. Hlineny and J. Kratochvil. We solve another open problem of P. Hlineny and J. Kratochvil by proving that the problem of finding Krausz dimension is NP-hard for split graphs and complements of bipartite graphs. We show that the problem of finding m-Krausz dimension is NP-hard for every m ≥ 1, but the problem "kdimm (G) ≤ k" is is fixed-parameter tractable when parameterized by k and m for (∝, 1)-polar graphs. Moreover, the class of (∝, 1)-polar graphs with kdimm (G) ≤ k is characterized by a finite list of forbidden induced subgraphs for every k, m≥ 1. [ABSTRACT FROM AUTHOR]