Search

Let G be a graph, and let Q(G) and L(G) denote the signless Laplacian matrix and the Laplacian matrix of G, respectively. The polynomials ϕ (Q (G) , x) = per (x I n - Q (G)) and ϕ (L (G) , x) = per (x I n - L (G)) are called signless Laplacian permanental polynomial and Laplacian permanental polynomial of G, respectively. In this paper, we investigate the properties of roots of ϕ (Q (G) , x) . We obtain the real root distribution of ϕ (Q (G) , x) . In particular, using the Gallai–Edmonds structure theorem, we determine the structures of graphs G whose roots of signless Laplacian permanental polynomial of G contain no positive integer p, where p is the minimum vertex degree of G. And we determine completely the graphs each of which having the multiplicity of the integer root p is equal to the deficiency of a maximum p-pendant structure of the graph. These results extend the conclusion obtained by Faria (Linear Algebra Appl 299:15–35, 1995). Furthermore, we give an algorithm to calculate the multiplicity of the root p of ϕ (Q (G) , x) . And we also determine the relation between the multiplicity of the root p of ϕ (Q (G) , x) and the matching number of G. Finally, we investigate the properties of roots of Laplacian permanental polynomial of non-bipartite graphs. And some open problems are presented. [ABSTRACT FROM AUTHOR]

In this paper, we apply the Turán sieve and the simple sieve developed by R. Murty and the first author to study problems in random graph theory. In particular, we obtain upper and lower bounds on the probability of a graph on n vertices having diameter 2 (or diameter 3 in the case of bipartite graphs) with edge probability p where the edges are chosen independently. An interesting feature revealed in these results is that the Turán sieve and the simple sieve "almost completely" complement each other. As a corollary to our result, we note that the probability of a random graph having diameter 2 approaches 1 as n → ∞ for constant edge probability p = 1 / 2 . [ABSTRACT FROM AUTHOR]

An independent set of a graph G is a vertex subset I such that there is no edge joining any two vertices in I. Imagine that a token is placed on each vertex of an independent set of G. The TS - ( TS k -) reconfiguration graph of G takes all non-empty independent sets (of size k) as its nodes, where k is some given positive integer. Two nodes are adjacent if one can be obtained from the other by sliding a token on some vertex to one of its unoccupied neighbors. This paper focuses on the structure and realizability of these reconfiguration graphs. More precisely, we study two main questions for a given graph G: (1) Whether the TS k -reconfiguration graph of G belongs to some graph class G (including complete graphs, paths, cycles, complete bipartite graphs, connected split graphs, maximal outerplanar graphs, and complete graphs minus one edge) and (2) If G satisfies some property P (including s-partitedness, planarity, Eulerianity, girth, and the clique's size), whether the corresponding TS - ( TS k -) reconfiguration graph of G also satisfies P , and vice versa. Additionally, we give a decomposition result for splitting a TS k -reconfiguration graph into smaller pieces. [ABSTRACT FROM AUTHOR]

For an n-vertex graph G, a fractional matching of G is a function f giving each edge a real number in [0, 1] such that ∑ e ∈ Γ (v) f (e) ≤ 1 for each vertex v ∈ V (G) , where Γ (v) is the set of edges incident to v. A fractional perfect matching is a fractional matching f with ∑ e ∈ E (G) f (e) = n 2 . In this paper, we establish tight lower bounds on the size and the spectral radius of G to guarantee that G has a fractional perfect matching, respectively. In addition, we investigate the relationship between fractional perfect matching and P ⩾ 2 -factor, and give some sufficient conditions for a graph to have a P ⩾ 2 -factor. [ABSTRACT FROM AUTHOR]

A graph H = (W , E H) is said to have bandwidth at most b if there exists a labeling of W as w 1 , w 2 , ⋯ , w n such that | i - j | ≤ b for every edge w i w j ∈ E H . We say that H is a balanced (β , Δ) -graph if it is a bipartite graph with bandwidth at most β | W | and maximum degree at most Δ , and it also has a proper 2-coloring χ : W → [ 2 ] such that | | χ - 1 (1) | - | χ - 1 (2) | | ≤ β | χ - 1 (2) | . In this paper, we prove that for every γ > 0 and every natural number Δ , there exists a constant β > 0 such that for every balanced (β , Δ) -graph H on n vertices we have R (H , H , C n) ≤ (3 + γ) n for all sufficiently large odd n. The upper bound is sharp for several classes of graphs. Let θ n , t be the graph consisting of t internally disjoint paths of length n all sharing the same endpoints. As a corollary, for each fixed t ≥ 1 , R (θ n , t , θ n , t , C n t + λ) = (3 t + o (1)) n , where λ = 0 if nt is odd and λ = 1 if nt is even. In particular, we have R (C 2 n , C 2 n , C 2 n + 1) = (6 + o (1)) n , which is a special case of a result of Figaj and Łuczak (2018). [ABSTRACT FROM AUTHOR]

In this paper, we apply the Turán sieve and the simple sieve developed by R. Murty and the first author to study problems in random graph theory. In particular, we obtain upper and lower bounds on the probability of a graph on n vertices having diameter 2 (or diameter 3 in the case of bipartite graphs) with edge probability p where the edges are chosen independently. An interesting feature revealed in these results is that the Turán sieve and the simple sieve "almost completely" complement each other. As a corollary to our result, we note that the probability of a random graph having diameter 2 approaches 1 as n → ∞ for constant edge probability p = 1 / 2 . [ABSTRACT FROM AUTHOR]

In this paper, we investigate a variant of Ramsey numbers called defective Ramsey numbers where cliques and independent sets are generalized to k-dense and k-sparse sets, both commonly called k-defective sets. We focus on the computation of defective Ramsey numbers restricted to some subclasses of perfect graphs. Since direct proof techniques are often insufficient for obtaining new values of defective Ramsey numbers, we provide a generic algorithm to compute defective Ramsey numbers in a given target graph class. We combine direct proof techniques with our efficient graph generation algorithm to compute several new defective Ramsey numbers in perfect graphs, bipartite graphs and chordal graphs. We also initiate the study of a related parameter, denoted by c k G (m) , which is the maximum order n such that the vertex set of any graph of order n in a class G can be partitioned into at most m subsets each of which is k-defective. We obtain several values for c k G (m) in perfect graphs and cographs. [ABSTRACT FROM AUTHOR]

Let T 1 , T 2 , … , T k be k (≥ 2) spanning trees of a graph G. The trees T 1 , T 2 , … , T k are completely independent if the paths connecting any two vertices of G in these k trees are pairwise internally disjoint. Sufficient conditions for a graph to possess k completely independent spanning trees have attracted popular attention intensively. In this paper, we focus on such sufficient conditions for bipartite graphs, and show that a bipartite graph G = (X ∪ Y , E) with order ν = m + n , m = | X | ≥ 2 k and n = | Y | ≥ m , has k completely independent spanning trees if for every pair of vertices x ∈ X , y ∈ Y , d (x) ≥ (k - 1) n k + 2 , d (y) ≥ (k - 1) m k + 2. Furthermore, we obtain that a bipartite graph G = (X ∪ Y , E) with order ν ≥ 8 , | X | ≥ 2 k and | Y | ≥ 2 k , has k completely independent spanning trees if the minimum degree δ (G) ≥ ⌊ (3 × 2 k - 2 - 1) ν 3 × 2 k - 1 ⌋ + 2 , or δ (G) ≥ (k - 1) ν 2 k + 2 and | X | = | Y |. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with order n and adjacency matrix A (G) . The characteristic polynomial of G is defined by ϕ (G ; λ) = det (λ I - A (G)) = ∑ i = 0 n a i (G) λ n - i , where a i (G) is called the i-th adjacency coefficient of G. Denote by B n , m the collection of all connected bipartite graphs having n vertices and m edges. A bipartite graph G is referred as 4-Sachs optimal if a 4 (G) = min { a 4 (H) ∣ H ∈ B n , m }. For any given integer pair (n, m), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite (n, m)-graphs for n ≥ 5 and n - 1 ≤ m ≤ 2 (n - 2) . Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020). [ABSTRACT FROM AUTHOR]

Henning et al. (Discrete Appl Math 162:399–403, 2014) proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 4 11 n . In this paper, we improve the 4 11 -bound to a 5 14 -bound, and prove that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 5 14 n . [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V (G) , E (G)) , the length of a shortest path from a vertex u to a vertex v is denoted by d(u, v). For a proper subset W of V(G), let m(W) be the maximum value of d(u, v) as u ranging over W and v ranging over V (G) \ W . The proper subset W = { w 1 , ... , w | W | } is a completeness-resolving set of G if Ψ W : V (G) \ W ⟶ [ m (W) ] | W | , u ⟼ (d (w 1 , u) , ... , d (w | W | , u)) is a bijection, where [ m (W) ] | W | = { (a (1) , ... , a (| W |)) ∣ 1 ≤ a (i) ≤ m (W) for each i = 1 , ... , | W | }. A graph is completeness-resolvable if it admits a completeness-resolving set. In this paper, we first construct the set of all completeness-resolvable graphs by using the edge coverings of some vertices in given bipartite graphs, and then establish posets on some subsets of this set by the spanning subgraph relationship. Based on each poset, we find the maximum graph and give the lower and upper bounds for the number of edges in a minimal graph. Furthermore, minimal graphs satisfying the lower or upper bound are characterized. [ABSTRACT FROM AUTHOR]

Let F be a family of graphs. A graph G is called F -free if for any F ∈ F , there is no subgraph of G isomorphic to F. Given a graph T and a family of graphs F , the generalized Turán number of F is the maximum number of copies of T in an F -free graph on n vertices, denoted by e x (n , T , F) . A linear forest is a graph whose connected components are all paths or isolated vertices. Let L n , k be the family of all linear forests of order n with k edges and K s , t ∗ be a graph obtained from K s , t by substituting the part of size s with a clique of order s. In this paper, we determine the exact values of e x (n , K s , L n , k) and e x (n , K s , t ∗ , L n , k) . Also, we study the case of this problem when the "host graph" is bipartite. Denote by e x bip (n , T , F) the maximum possible number of copies of T in an F -free bipartite graph with each part of size n. We determine the exact value of e x bip (n , K s , t , L n , k) . Our proof is mainly based on the shifting method. [ABSTRACT FROM AUTHOR]

Let D be a strong balanced bipartite digraph on 2a vertices. For x , y , z ∈ V (D) , if x → z and y → z , then we call the pair { x , y } dominating; if z → x and z → y , then we call the pair { x , y } dominated. In 2017, Adamus [Graphs and Combinatorics, 33(2017) 43–51] proved that if d (x) + d (y) ≥ 3 a whenever { x , y } is a dominating or dominated pair, then D is Hamiltonian. In 2021, Adamus [Discrete Mathematics, 344(3) (2021) 112240] proved that if only every dominating pair of vertices { x , y } in D satisfies d (x) + d (y) ≥ 3 a + 1 , then D is Hamiltonian. In this paper, we show that the same conclusion is reached if we replace 3 a + 1 with 3a in the above condition. The lower bound for 3a is sharp. [ABSTRACT FROM AUTHOR]

We study the list chromatic number of the Cartesian product of any graph G and a complete bipartite graph with partite sets of size a and b, denoted χ ℓ (G □ K a , b) . We have two motivations. A classic result on the gap between list chromatic number and the chromatic number tells us χ ℓ (K a , b) = 1 + a if and only if b ≥ a a . Since χ ℓ (K a , b) ≤ 1 + a for any b ∈ N , this result tells us the values of b for which χ ℓ (K a , b) is as large as possible and far from χ (K a , b) = 2 . In this paper we seek to understand when χ ℓ (G □ K a , b) is far from χ (G □ K a , b) = max { χ (G) , 2 } . It is easy to show χ ℓ (G □ K a , b) ≤ χ ℓ (G) + a . Borowiecki et al. (Discrete Math 306:1955–1958, 2006) showed that this bound is attainable if b is sufficiently large; specifically, χ ℓ (G □ K a , b) = χ ℓ (G) + a whenever b ≥ (χ ℓ (G) + a - 1) a | V (G) | . Given any graph G and a ∈ N , we wish to determine the smallest b such that χ ℓ (G □ K a , b) = χ ℓ (G) + a . In this paper we show that the list color function, a list analogue of the chromatic polynomial, provides the right concept and tool for making progress on this problem. Using the list color function, we prove a general improvement on Borowiecki et al.'s (2006) result, and we compute the smallest such b for some large families of chromatic-choosable graphs. [ABSTRACT FROM AUTHOR]

For a graph G, define σ 2 (G) by σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) } . If G is a bipartite graph with partite sets X and Y, we also define σ 1 , 1 (G) by σ 1 , 1 (G) = min { d G (x) + d G (y) : x ∈ X , y ∈ Y , x y ∉ E (G) } . Ore's theorem states that a graph of order n ≥ 3 with σ 2 (G) ≥ n contains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graph G of order 2 n ≥ 4 with σ 1 , 1 (G) ≥ n + 1 contains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore's theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore's theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore's theorem. [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow (or heterochromatic) if all its edges have distinct colors. It is known that if an edge-colored connected graph H has minimum color degree at least |H|/2 and has a certain property, then H has a rainbow spanning tree. In this paper, we prove that if an edge-colored connected bipartite graph G has minimum color degree at least |G|/3 and has a certain property, then G has a rainbow spanning tree. We also give a similar sufficient condition for G to have a properly colored spanning tree. Moreover, we show that these minimum color-degree conditions are sharp. [ABSTRACT FROM AUTHOR]

A graph G is said to be distanced matchable if, for any matching M of G in which edges are pairwise at least distance d apart, there exists a perfect matching M ∗ of G which contains M. In this paper, we prove the following results: (i) if G is a cubic bipartite graph in which, for each e ∈ E (G) , there exist two cycles C 1 , C 2 of length at most d such that E (C 1) ∩ E (C 2) = { e } , then G is distance d - 1 matchable, and (ii) if G is a planar or projective planar cubic bipartite graph in which, for each e ∈ E (G) , there exist two cycles C 1 , C 2 of length at most 6 such that e ∈ E (C 1) ∩ E (C 2) , then G is distance 6 matchable. [ABSTRACT FROM AUTHOR]

In the Partition Into Complementary Subgraphs (Comp-Sub) problem we are given a graph G = (V , E) , and an edge set property Π , and asked whether G can be decomposed into two graphs, H and its complement H ¯ , for some graph H, in such a way that the edge cut-set (of the cut) [ V (H) , V (H ¯) ] satisfies property Π . Such a problem is motivated by the fact that several parameterized problems are trivially fixed-parameter tractable when the input graph G is decomposable into two complementary subgraphs. In addition, it generalizes the recognition of complementary prism graphs, and it is related to graph isomorphism when the desired cut-set is empty, Comp-Sub(∅ ). In this paper we are particularly interested in the case Comp-Sub(∅ ), where the decomposition also partitions the set of edges of G into E(H) and E (H ¯) . When the input is a chordal graph, we show that Comp-Sub(∅ ) is GI - complete , that is, polynomially equivalent to Graph Isomorphism. But it becomes more tractable than Graph Isomorphism for several subclasses of chordal graphs. We present structural characterizations for split, starlike, block, and unit interval graphs. We also obtain complexity results for permutation graphs, cographs, comparability graphs, co-comparability graphs, interval graphs, co-interval graphs and strongly chordal graphs. Furthermore, we present some remarks when Π is a general edge set property and the case when the cut-set M induces a complete bipartite graph. [ABSTRACT FROM AUTHOR]

It is well known that a graph is bipartite if and only if it contains no odd cycles. Gallai characterized edge colorings of complete graphs containing no properly colored triangles in recursive sense. In this paper, we completely characterize edge-colored complete graphs containing no properly colored odd cycles and give an efficient algorithm with complexity O (n 3) for deciding the existence of properly colored odd cycles in an edge-colored complete graph of order n. Moreover, we show that for two integers k, m with m ⩾ k ⩾ 3 , where k - 1 and m are relatively prime, an edge-colored complete graph contains a properly colored cycle of length ℓ ≡ k (mod m) if and only if it contains a properly cycle of length ℓ ′ ≡ k (mod m) , where ℓ ′ < 2 m 2 (k - 1) + 3 m . [ABSTRACT FROM AUTHOR]

A subgroup G of the automorphism group of a graph Γ acts half-arc-transitively on Γ if the natural actions of G on the vertex-set and edge-set of Γ are both transitive, but the natural action of G on the arc-set of Γ is not transitive. When G = Aut (Γ) the graph Γ is said to be half-arc-transitive. Given a bipartite cubic graph with a certain degree of symmetry two covering constructions that provide infinitely many tetravalent graphs admitting half-arc-transitive groups of automorphisms are introduced. Symmetry properties of constructed graphs are investigated. In the second part of the paper the two constructions are applied to the Heawood graph, the well-known incidence graph of the Fano plane. It is proved that the members of the infinite family resulting from one of the two constructions are all half-arc-transitive, and that the infinite family resulting from the second construction contains a mysterious family of arc-transitive graphs that emerged within the classification of tightly attached half-arc-transitive graphs of valence 4 back in 1998 and 2008. [ABSTRACT FROM AUTHOR]

The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph G 1 □ G 2 of graphs G 1 and G 2 satisfying that G 1 is traceable and G 2 is connected with a path factor. Let P n be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) P n □ H is Hamiltonian; (ii) P n □ H is 1-tough; and (iii) H has a path factor. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, it is said that G percolates in H-bootstrap process if one could join all the nonadjacent pairs of vertices of G in some order such that a new copy of H is created at each step. Balogh, Bollobás and Morris in 2012 investigated the threshold of H-bootstrap percolation in the Erdős–Rényi model for the complete graph H and proposed the similar problem for H = K s , t , the complete bipartite graph. In this paper, we provide lower and upper bounds on the threshold of K 2 , t -bootstrap percolation. In addition, a threshold function is derived for K 2 , 4 -bootstrap percolation. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G ≇ K 3 , 3 is a connected, cubic, bipartite graph on n vertices, then i (G) ≤ 4 11 n . Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K 2 , 3 . [ABSTRACT FROM AUTHOR]

For given graphs G1,G2,...,Gk,k≥2, the multicolor Ramsey numberR(G1,G2,...,Gk) is the smallest integer n such that if we arbitrarily color the edges of the complete graph of order n with k colors, then it contains a monochromatic copy of Gi in color i, for some 1≤i≤k. The main result of the paper is a theorem which establishes the connection between the multicolor Ramsey number and the appropriate multicolor bipartite Ramsey number together with the ordinary Ramsey number. The remaining part of the paper consists of a number of corollaries which are derived from the main result and from known results for Ramsey numbers and bipartite Ramsey numbers. We provide some new exact values or generalize known results for multicolor Ramsey numbers of paths, cycles, stripes and stars versus other graphs. [ABSTRACT FROM AUTHOR]

Let T be a tree with m edges. It was conjectured that every m-regular bipartite graph can be decomposed into edge-disjoint copies of T. In this paper, we prove that every 6-regular bipartite graph can be decomposed into edge-disjoint paths with 6 edges. As a consequence, every 6-regular bipartite graph on n vertices can be decomposed into n 2 paths, which is related to the well-known Gallai's Conjecture: every connected graph on n vertices can be decomposed into at most n + 1 2 paths. [ABSTRACT FROM AUTHOR]

Let G be a balanced bipartite graph with bipartite sets X, Y. We say that G is Hamilton-biconnected if there is a Hamilton path connecting any vertex in X and any vertex in Y. We define the bipartite independent number α B o (G) to be the maximum integer α such that for any integer partition α = s + t , G has an independent set formed by s vertices in X and t vertices in Y. In this paper we show that if α B o (G) ≤ δ (G) then G is Hamilton-biconnected, unless G has a special construction. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a finite connected graph along with a coloring of the vertices of G using the colors in a given set X. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the multi-color forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research. [ABSTRACT FROM AUTHOR]

An edge labeling of a connected graph G = (V , E) is said to be local antimagic if it is a bijection f : E → { 1 , ... , | E | } such that for any pair of adjacent vertices x and y, f + (x) ≠ f + (y) , where the induced vertex label f + (x) = ∑ f (e) , with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by χ la (G) , is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, we give counterexamples to the lower bound of χ la (G ∨ O 2) that was obtained in [Local antimagic vertex coloring of a graph, Graphs Combin. 33:275–285 (2017)]. A sharp lower bound of χ la (G ∨ O n) and sufficient conditions for the given lower bound to be attained are obtained. Moreover, we settled Theorem 2.15 and solved Problem 3.3 in the affirmative. We also completely determined the local antimagic chromatic number of complete bipartite graphs. [ABSTRACT FROM AUTHOR]

In this paper, we focus on a so-called Fan-type condition assuring us the existence of long paths in bipartite graphs. As a consequence of our main result, we completely determine the bipartite Ramsey numbers b (P s , B t 1 , t 2 ) , where B t 1 , t 2 is the graph obtained from a t 1 -star and a t 2 -star by joining their centers. [ABSTRACT FROM AUTHOR]

Finding the multiplicity of cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. Recently, Blake and Lin computed the number of shortest cycles (g-cycles, where g is the girth of the graph) in a bi-regular bipartite graph, in terms of the degree sequences and the spectrum (eigenvalues of the adjacency matrix) of the graph (Blake and Lin in IEEE Trans Inf Theory 64(10): 6526–6535, 2018). This result was subsequently extended in Dehghan and Banihashemi (IEEE Trans Inf Theory 65(6):3778–3789, 2019) to cycles of length g + 2 , ... , 2 g - 2 , in bi-regular bipartite graphs, as well as 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with g ≥ 4 and g ≥ 6 , respectively. In this paper, we complement these positive results with negative results demonstrating that the information of the degree sequences and the spectrum of a bipartite graph is, in general, insufficient to count (a) the i-cycles, i ≥ 2 g , in bi-regular graphs, (b) the i-cycles for any i > g , regardless of the value of g, and g-cycles for g ≥ 6 , in irregular graphs, and (c) the i-cycles for any i > g , regardless of the value of g, and g-cycles for g ≥ 8 , in half-regular graphs. To obtain these results, we construct counter-examples using the Godsil–McKay switching. [ABSTRACT FROM AUTHOR]

In this paper we construct a class of bounded degree bipartite graphs with a small separator and large bandwidth, thereby showing that separability and bandwidth are not linearly equivalent. Furthermore, we also prove that graphs from this class are spanning subgraphs of graphs with minimum degree just slightly above n / 2, even though their bandwidth is large. [ABSTRACT FROM AUTHOR]

In this paper, a formula for the Ihara zeta function of the cone over a semiregular bipartite graph is derived. Using this formula, we show that two cones over semiregular bipartite graphs are cospectral if and only if they have the same Ihara zeta function. Moreover, the convergence of the zeta function of this family of graphs is considered. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G is a set D ⊆ V G such that every vertex in V G - D is adjacent to at least one vertex in D, and the domination number γ (G) of G is the minimum cardinality of a dominating set of G. In this paper we provide a new characterization of bipartite graphs whose domination number is equal to the cardinality of its smaller partite set. Our characterization is based upon a new graph operation. [ABSTRACT FROM AUTHOR]

Indicated coloring is a type of game coloring in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben's strategy) is called the indicated chromatic number of G, denoted by χ i (G) . In this paper, we obtain structural characterization of { P 5 , K 4 , K i t e , B u l l } -free graphs and connected { P 6 , C 5 , K 1 , 3 } -free graphs that contain an induced C 6 . Also, we prove that { P 5 , K 4 , K i t e , B u l l } -free graphs and connected { P 6 , C 5 , P 5 ¯ , K 1 , 3 } -free graphs which contain an induced C 6 are k-indicated colorable for all k ≥ χ (G) . In addition, we show that, if m ≥ 1 and G is a bipartite graph, then χ i (K [ G ] (m , m , ... , m)) = χ (K [ G ] (m , m , ... , m)) . Further, we show that K [ C 5 ] is k-indicated colorable for all k ≥ χ (G) and as a consequence, we exhibit that { P 2 ∪ P 3 , C 4 } -free graphs, { P 5 , C 4 } -free graphs are k-indicated colorable for all k ≥ χ (G) . This partially answers one of the questions which was raised by Grzesik (Discret Math 312:3467–3472, 2012). [ABSTRACT FROM AUTHOR]

A subgraph H of an edge-colored graph G is rainbow if all of its edges have different colors. The anti-Ramsey number is the maximum number of colors in an edge-coloring of G with no rainbow copy of H. Originally a complete graph was considered as G. In this paper, we consider a complete bipartite graph as the host graph and discuss some results for the graph H being hamiltonian cycle and perfect matching. Let c (K p , p , t) and m (K p , p , t) be the maximum number of colors in an edge-coloring of the complete bipartite graph K p , p not having t edge-disjoint rainbow hamiltonian cycles and perfect matchings, respectively. We prove that c (K p , p , t) = p 2 - p + t for t ≥ 2 , p ≥ 4 t - 1 and m (K p , p , t) = p 2 - 2 p + t + 1 for t ≥ 2, p ≥ 2 t + 8 . [ABSTRACT FROM AUTHOR]

Let G be a plane elementary bipartite graph with more than one finite face. We first characterize forcing edges and anti-forcing edges of G in terms of handles and forcing faces. We then introduce the concept of a nice pair of faces of G, which allows us to provide efficient algorithms to construct plane minimal elementary bipartite graphs from G. We show that if G ′ is a minimal elementary spanning subgraph of G, then all vertices of a forcing face of G are contained in a forcing face of G ′ , and any forcing face of G is a forcing face of G ′ if it is still a face of G ′ . Furthermore, any forcing edge (resp., anti-forcing edge) of G is still a forcing edge (resp., an anti-forcing edge) of G ′ if it is still an edge of G ′ . We conclude the paper with the co-existence property of forcing edges and anti-forcing edges for those plane minimal elementary bipartite graphs that remain 2-connected when any handle of length one (if exists) is deleted. [ABSTRACT FROM AUTHOR]

In 1957 Hugo Steinhaus published an elementary, recreational problem concerning a configuration of rooks on the chessboard (Steinhaus in Matematyka, czasopismo dla nauczycieli 1:55, 1957). Over the last 60 years, this problem has achieved quite a peculiar status: apparently, it had two (both published) solutions—one short and elegant (Steinhaus in Sto zadań [One Hundred Problems], PWN, Warszawa, 1958), but (as it soon turned out) incorrect (Zadania konkursowe, Rozwiązania [Competition problems, Solutions]. Matematyka, Czasopismo dla nauczycieli 4-6:62-65, 1958); while the other (Zadania konkursowe, 1958) (Steinhaus in One Hundred Problems in Elementary Mathematics. Popular Lectures in Mathematics, Pergamon Press, Oxford and PWN, Warszawa, 1963)—known internationally, yet long and complex, so probably never read (except, perhaps, by its author) and never checked for its correctness. It was only in 2004 when a correct and short solution of the original Steinhaus' problem was found and published (Morawiec in Matematyka Czasopismo dla nauczycieli 2:46-50, 2004). The solution involved the well-known Hall's 'marriage' theorem (Wilson in Introduction to Graph Theory, Longman, Harlow, 1996, p. 113). Further investigation has shown that the connection between Steinhaus' problem and Hall's theorem runs deeper than the use of the latter in the solution of the former. In this paper we present the results of this investigation, by the way defining a simple but seemingly new class of special matchings (ibid.) in bipartite graphs (id., p. 18). [ABSTRACT FROM AUTHOR]

The Turán type extremal problems ask to maximize the number of edges over all graphs which do not contain fixed subgraphs. Similarly, their spectral counterparts ask to maximize spectral radius of all graphs which do not contain fixed subgraphs. In this paper, we determine the maximum spectral radius of all graphs without a linear forest as a subgraph and all the extremal graphs. In addition, the maximum number of edges and spectral radius of all bipartite graphs without k·P3 as a subgraph are obtained and all the extremal graphs are also determined. Moreover, some relations between Turán type extremal problems and their spectral counterparts are discussed. [ABSTRACT FROM AUTHOR]

An odd (resp. even) subgraph in a multigraph is its subgraph in which every vertex has odd (resp. even) degree. We say that a multigraph can be decomposed into two odd subgraphs if its edge set can be partitioned into two sets so that both form odd subgraphs. In this paper we give a necessary and sufficient condition for thedecomposability of a multigraph into two odd subgraphs. We also present a polynomial time algorithm for finding such a decomposition or showing its non-existence. We also deal with the case of the decomposability into an even subgraph and an odd subgraph. [ABSTRACT FROM AUTHOR]

The neighborhood complex of a graph is the family of subsets of open neighborhoods of its vertices. The neighborhood polynomial is the ordinary generating function for the number of sets of the neighborhood complex with respect to their cardinality. This paper provides a new representation of the neighborhood polynomial as a sum over complete bipartite subgraphs of a graph. Using the close relation between the domination polynomial and the neighborhood polynomial of a graph, we can also give a new presentation of the domination polynomial. Finally we show that finding the number of certain double cliques of a graph is sufficient to determine the number of dominating sets of a graph. [ABSTRACT FROM AUTHOR]

An octad triple is a set of three octads, octads being the blocks of the S(5, 8, 24) Steiner system. In this paper we determine the orbits of M24, the largest Mathieu group, upon the set of octad triples. [ABSTRACT FROM AUTHOR]

A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called Ni-locally connected if G[{x∈V(G):1≤dG(w,x)≤i}] is connected and N2-locally connected if G[{uv:{uw,vw}⊆E(G)}] is connected for every vertex w of G, respectively. In this paper, we prove the following.Every 2-connected P7-free graph of minimum degree at least three other than the Petersen graph has a spanning Eulerian subgraph. This implies that every H-free 3-connected graph (or connected N4-locally connected graph of minimum degree at least three) other than the Petersen graph is supereulerian if and only if H is an induced subgraph of P7, where Pi is a path of i vertices.Every 2-edge-connected H-free graph other than {K2,2k+1:kis a positive integer} is supereulerian if and only if H is an induced subgraph of P4.If every connected H-free N3-locally connected graph other than the Petersen graph of minimum degree at least three is supereulerian, then H is an induced subgraph of P7 or T2,2,3, i.e., the graph obtained by identifying exactly one end vertex of P3,P3,P4, respectively.If every 3-connected H-free N2-locally connected graph is hamiltonian, then H is an induced subgraph of K1,4. We present an algorithm to find a collapsible subgraph of a graph with girth 4 whose idea is used to prove our first conclusion above. Finally, we propose that the reverse of the last two items would be true. [ABSTRACT FROM AUTHOR]

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. Bolloba´s and Scott proved that every regular graph with m edges admits a balanced bipartition V1, V2 of V(G) such that max{e(V1),e(V2)}

Many extremal problems for graphs have threshold graphs as their extremal examples. For instance the current authors proved that for fixed k≥1, among all graphs on n vertices with e edges, some threshold graph has the fewest matchings of size k; indeed either the lex graph or the colex graph is such an extremal example. In this paper we consider the problem of maximizing the number of matchings in the class of threshold graphs. We prove that the minimizers are what we call almost alternating threshold graphs. We also discuss a problem with a similar flavor: which threshold graph has the fewest independent sets. Here we are inspired by the result that among all graphs on n vertices and e edges the lex graph has the most independent sets. [ABSTRACT FROM AUTHOR]

In this paper, we first show that every (P6, diamond, K4)-free graph is 6-colorable. We also give an example of a (P6, diamond, K4)-free graph G with χ(G)=6. Further, we show that for every (P6, diamond)-free graph G, the chromatic number of G is upper bounded by a linear function of its clique number. This generalizes some known results in the literature. [ABSTRACT FROM AUTHOR]

Las Vergnas (CR Acad Sci Paris Sér A 272:1297-1300, 1971), and Broersma and Tuinstra (J Graph Theory 29:227-237, 1998) independently investigated a degree sum condition for a graph to have a spanning tree whose number of leaves is restricted. In this paper, we obtain the bipartite analogy of this result. [ABSTRACT FROM AUTHOR]

A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well as handle any vertex recoloring requests. Our main concern is the greedy approach and characterization of graph classes for which it is possible to decide in polynomial time whether for the fixed forbidden graph F and positive integer k the greedy algorithm ever uses more than k colors in dynamic F-free coloring. For various classes of graphs we give such characterizations in terms of a finite number of minimal forbidden graphs thus solving the above-mentioned problem for the so-called F-trees when F is 2-connected, and for classical trees, when F is a path of order 3 (the latter variant is also known as subcoloring or 1-improper coloring). [ABSTRACT FROM AUTHOR]

The strong geodetic problem is a recent variation of the classical geodetic problem. For a graph G, its strong geodetic number sg(G) is the cardinality of a smallest vertex subset S, such that each vertex of G lies on one fixed shortest path between a pair of vertices from S. In this paper, some general properties of the strong geodetic problem are studied, especially in connection with the diameter of a graph. The problem is also solved for balanced complete bipartite graphs. [ABSTRACT FROM AUTHOR]

Given a graph H, we say a graph G is H-saturated if G does not contain H as a subgraph and the addition of any edge e′∉E(G) results in H as a subgraph. In this paper, we construct (K4-e)-saturated graphs with |E(G)| either the size of a complete bipartite graph, a 3-partite graph, or in the interval 2n-4,n2n2-n+6. We then extend the (K4-e)-saturated graphs to (Kt-e)-saturated graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider uniformly resolvable decompositions of complete graph $$K_v$$ (or $$K_v$$ minus a 1-factor I for even v) into cycles. We will focus on the existence of factorizations of $$K_v$$ or $$K_v-I$$ containing up to four non-isomorphic factors. We obtain all possible solutions for uniform factors involving 4, m, 2 m and 4 m-cycles with a few possible exceptions when m is odd. [ABSTRACT FROM AUTHOR]