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]

Let S be a set of at least two vertices in a graph G. A subtree T of G is an S -Steiner tree if S ⊆ V (T). Two S -Steiner trees T 1 and T 2 are internally disjoint (resp. edge-disjoint) if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S (resp. E (T 1) ∩ E (T 2) = 0̸). Let κ G (S) (resp. λ G (S)) be the maximum number of internally disjoint (resp. edge-disjoint) S -Steiner trees in G , and let κ k (G) (resp. λ k (G)) be the minimum κ G (S) (resp. λ G (S)) for S ranges over all k -subsets of V (G). It is well-known that the connectivity of the line graph of a graph G is closely related to the edge-connectivity of G. Chartrand et al., Li et al., and Li et al. showed that κ k (L (G)) ≥ λ k (G) for k = 2 , 3 , 4 , respectively. In [Discrete Math. 341(2018), 1945–1951.], Li et al. also proposed the following conjecture: κ k (L (G)) ≥ λ k (G) for integer k ≥ 2 and a graph G with at least k vertices. In this paper, we show that κ k (L (G)) ≥ λ k (G) − m a d (G) 2 2 for general k , where m a d (G) is the maximum average degree of a graph G. We also show that κ k (L (G)) ≥ λ k (G) − r 2 2 for any integers k and r such that k ≤ r 2 . Finally, we show that the conjecture holds for k = 5 , and the conjecture holds for the wheel graph and the complete bipartite graph K 3 , n. [ABSTRACT FROM AUTHOR]

Abstract: Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311–320.] introduced -graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let and d be non-negative integers such that and is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an -graph. Liu and Yu''s Papee''s paper, the recursive relations for distinct parameters and d were presented and the impact of adding or deleting an edge also was discussed for the case . In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for -graphs in the general case . [Copyright &y& Elsevier]

An edge-coloured path is rainbow if its edges have distinct colours. For a connected graph G , the rainbow connection number (resp. strong rainbow connection number ) of G is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by a rainbow path (resp. rainbow geodesic). These two graph parameters were introduced by Chartrand, Johns, McKeon, and Zhang in 2008. Krivelevich and Yuster generalised this concept to the vertex-coloured setting. Similarly, Liu, Mestre, and Sousa introduced the version which involves total-colourings. Dorbec, Schiermeyer, Sidorowicz, and Sopena extended the concept of the rainbow connection to digraphs. In this paper, we consider the (strong) total rainbow connection number of digraphs. Results on the (strong) total rainbow connection number of biorientations of graphs, tournaments, and cactus digraphs are presented. [ABSTRACT FROM AUTHOR]

An arc-coloured digraph D is alternating if whenever ( u , v ) and ( v , w ) are arcs in D they are of different colours. In an arc coloured digraph D , a subset K ⊂ V ( D ) of vertices of D is a kernel by alternating paths (or alternating kernel ) if it is absorbent and independent by directed alternating paths. In this paper we prove sufficient conditions for the existence of alternating kernels in arc-coloured tournaments, quasi-transitive digraphs, and k -partite digraphs. [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]

For a graph G , we denote by σ 2 ( G ) the minimum degree sum of two non-adjacent vertices if G is non-complete; otherwise, σ 2 ( G ) = + ∞ . In this paper, we prove the following two results: (i) If s 1 , s 2 ≥ 2 are integers and G is a non-complete graph with σ 2 ( G ) ≥ 2 ( s 1 + s 2 + 1 ) − 1 , then G contains two vertex-disjoint subgraphs H 1 and H 2 such that each H i is a graph of order at least s i + 1 with σ 2 ( H i ) ≥ 2 s i − 1 . (ii) If s 1 , s 2 ≥ 2 are integers and G is a triangle-free graph of order at least 3 with σ 2 ( G ) ≥ 2 ( s 1 + s 2 ) − 1 , then G contains two vertex-disjoint subgraphs H 1 and H 2 such that each H i is a graph of order at least 2 s i with σ 2 ( H i ) ≥ 2 s i − 1 . By using this result, we also give some corollaries concerning degree conditions for the existence of k vertex-disjoint cycles. [ABSTRACT FROM AUTHOR]

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: The Grundy (or First-Fit) chromatic number of a graph is the maximum number of colors used by the First-Fit coloring of the graph . In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number. [Copyright &y& Elsevier]

Abstract: Let denote the number of odd components of a graph G. The deficiency of G is defined as , and this equals the number of vertices unmatched by any maximum matching of G. A subset is called a Tutte set (or barrier set) of G if , and an extreme set if . Recently a graph operator, called the D-graph , was defined that has proven very useful in examining Tutte sets and extreme sets of graphs which contain a perfect matching. In this paper we give two natural and related generalizations of the D-graph operator to all simple graphs, both of which have analogues for many of the interesting and useful properties of the original. [Copyright &y& Elsevier]

Abstract: The behavior of the disjunctive operator, defined by Balas, Ceria and Cornuéjols, in the context of the “antiblocker duality diagram” associated with the stable set polytope, QSTAB(G), of a graph and its complement, was first studied by Aguilera, Escalante and Nasini. The authors prove the commutativity of this diagram in any number of iterations of the disjunctive operator. One of the main consequences of this result is a generalization of the Perfect Graph Theorem under the disjunctive rank. In the same context, Lipták and Tunçel study the lift-and-project operators , N and defined by Lovász and Schrijver. They find a graph for which the diagram does not commute in one iteration of the - and N-operator. In connection with , the authors implicitly suggest a similar result proving that if the diagram commutes in iterations, . In this paper, we give for any number of iterations, explicit proofs of the non commutativity of the -, N- and -diagram. In the particular case of the - and N-operator, we find bounds for the ranks of the complements of line graphs (of complete graphs), which allow us to prove that the diagrams do not commute for these graphs. [Copyright &y& Elsevier]

Abstract: The generalized Mycielskians (also known as cones over graphs) are the natural generalization of the Mycielski graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer , one can transform G into a new graph , the generalized Mycielskian of G. This paper investigates circular clique number, total domination number, open packing number, fractional open packing number, vertex cover number, determinant, spectrum, and biclique partition number of . [Copyright &y& Elsevier]

Abstract: In this paper we introduce a chromatic parameter, called the fixing chromatic number, which is related to unique colourability of graphs, in the sense that it measures how one can embed the given graph G in by adding edges between G and to make the whole graph uniquely t-colourable. We study some basic properties of this parameter as well as its relationships to some other well-known chromatic numbers as the acyclic chromatic number. We compute the fixing chromatic number of some graph products by applying a modified version of the exponential graph construction. [Copyright &y& Elsevier]

Abstract: In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced . For a graph on vertices and edges, both our cograph recognition and cotree construction algorithms run in time and require processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal -time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal -time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced ) whenever our algorithms decide that the input graphs are not cographs. [Copyright &y& Elsevier]

Abstract: Probe interval graphs (PIGs) are used as a generalization of interval graphs in physical mapping of DNA. is a probe interval graph (PIG) with respect to a partition of V if vertices of G correspond to intervals on a real line and two vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is in P; vertices belonging to P are called probes and vertices belonging to N are called non-probes. One common approach to studying the structure of a new family of graphs is to determine if there is a concise family of forbidden induced subgraphs. It has been shown that there are two forbidden induced subgraphs that characterize tree PIGs. In this paper we show that having a concise forbidden induced subgraph characterization does not extend to 2-tree PIGs; in particular, we show that there are at least 62 minimal forbidden induced subgraphs for 2-tree PIGs. [Copyright &y& Elsevier]

Abstract: Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. It is shown in this paper that the classes of interval graphs and permutation graphs enjoy such a distance labeling scheme using bit labels on n-vertex graphs. Towards establishing these results, we present a general property for graphs, called well--separation, and show that graph classes satisfying this property have bit labeling schemes. In particular, interval graphs are well--separated and permutation graphs are well--separated. [Copyright &y& Elsevier]

We study the following Constrained Bipartite Edge Coloring problem: We are given a bipartite graph G=(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard even for bipartite graphs of maximum degree three. Two special cases of the problem have been previously considered and tight upper and ower bounds on the optimal number of colors were proved. The upper bounds led to 3/2-approximation algorithms for both problems. In this paper we present a randomized (1.37+o(1))-approximation algorithm for the general problem in the case where max{l,c}=ω(ln n). Our techniques are motivated by recent works on the Circular Arc Coloring problem and are essentially different and simpler than the existing ones. [Copyright &y& Elsevier]

In this paper, we present an integer programming formulation of the prize collecting Steiner problem in graphs (PCSPG) and describe an algorithm to obtain lower bounds for the problem. The algorithm is based on polyhedral cutting planes and is initiated with tests that attempt to reduce the size of the input graph. Computational experiments were carried out to evaluate the strength of the formulation through its linear programming relaxation. On 96 out of the 114 instances tested, integer solutions were found (thus generating optimal PCSPG solutions). [Copyright &y& Elsevier]

In this paper we characterize the class of plane graphs that can be embedded on the two-dimensional grid with at most one bend on each edge. In addition, we provide an algorithm that either detects a forbidden configuration or generates an embedding with at most one bend on each edge. [Copyright &y& Elsevier]

In this paper we decompose odd-hole-free graphs (graphs that do not contain as an induced subgraph a chordless cycle of odd length greater than three) with double star cutsets and 2-joins into bipartite graphs, line graphs of bipartite graphs and the complements of line graphs of bipartite graphs. [Copyright &y& Elsevier]

Let H be a graph on n vertices and G a collection of n subgraphs of H, one for each vertex. Then G is an orthogonal double cover (ODC) of H if every edge of H occurs in exactly two members of G and any two members share an edge whenever the corresponding vertices are adjacent in H. ODCs of complete graphs have been widely studied in literature. In this paper we are concerned with ODCs of arbitrary graphs. In particular, we investigate the existence of ODCs whose members are isomorphic sets of independent edges. [Copyright &y& Elsevier]

Abstract: For a given connected graph G of order n, a routing R is a set of elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of a graph is the maximum number of paths of R passing through any vertex (resp. edge) in the graph. In this paper, the authors determine the vertex and the edge forwarding indices of a folded n-cube as and , respectively. [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]