Search

Let G be an undirected bipartite graph with positive integer weights on the edges. We refine the existing decomposition theorem originally proposed by Kao et al., for computing maximum weight bipartite matching. We apply it to design an efficient version of the decomposition algorithm to compute the weight of a maximum weight bipartite matching of G in O(\sqrt{|V|}W'/k(|V|,W'/N))-time by employing an algorithm designed by Feder and Motwani as a subroutine, where |V| and N denote the number of nodes and the maximum edge weight of G, respectively and k(x,y)=log(x) /log(x^2/y). The parameter W' is smaller than the total edge weight W, essentially when the largest edge weight differs by more than one from the second-largest edge weight in the current working graph in any decomposition step of the algorithm. In best the case, W'=O(|E|) where |E| is the number of edges of G and in the worst case, W'=W, that is, |E| \leq W' \leq W. In addition, we talk about a scaling property of the algorithm and research a better bound of the parameter W'. Experimental evaluations of randomly generated data show that the proposed improvement is significant in general.

A graph G = ( V , E ) is weighted- k -antimagic if for each w : V → R , there is an injective function f : E → { 1 , … , | E | + k } such that the following sums are all distinct: for each vertex u , ∑ v : u v ∈ E f ( u v ) + w ( u ) . When such a function f exists, it is called a ( w , k ) -antimagic labeling of G . A connected graph G is antimagic if it has a ( w 0 , 0 ) -antimagic labeling, for w 0 ( u ) = 0 , for each u ∈ V . In this work, we prove that all the complete bipartite graphs K p , q , are weighted- 0 -antimagic when 2 ≤ p ≤ q and q ≥ 3 . Moreover, an algorithm is proposed that computes in polynomial time a ( w , 0 ) -antimagic labeling of the graph. Our result implies that if H is a complete partite graph, with H ≠ K 1 , q , K 2 , 2 , then any connected graph G containing H as a spanning subgraph is antimagic.

Let G of order n be the vertex-disjoint union of two cycles. It is known that there exists a G -decomposition of K v for all v ≡ 1 ( mod 2 n ) . If G is bipartite and x is a positive integer, it is also known that there exists a G -decomposition of K n x − I , where I is a 1-factor. If G is not bipartite, there exists a G -decomposition of K n if n is odd, and of K n − I , where I is a 1-factor, if n is even. We use novel extensions of the Bose construction for Steiner triple systems and some recent results on the Oberwolfach Problem to obtain a G -decomposition of K v for all v ≡ n ( mod 2 n ) when n is odd, unless G = C 4 ∪ C 5 and v = 9 . If G consists of two odd cycles and n ≡ 0 ( mod 4 ) , we also obtain a G -decomposition of K v − I , for all v ≡ 0 ( mod n ) , v ≠ 4 n .

We investigate the terminal-pairibility problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of $\Delta(D)$ which still guarantees that the demand graph $D$ is terminal-pairable in this setting. We also prove a sharp theorem on the maximum number of edges such a demand graph can have., Comment: 8 pages, several typos corrected

Let G be a simple m × n bipartite graph with m ≥ n . We prove that if the minimum degree of G satisfies δ ( G ) ≥ m ∕ 2 + 1 , then G is bipanconnected: for every pair of vertices x , y , and for every appropriate integer 2 ≤ l ≤ 2 n , there is an x , y -path of length l in G .

Inspired by previous work of Balogh (2006), we show that, given r ≥ 5 and n large, the balanced complete bipartite graph K n ∕ 2 , n ∕ 2 is the n -vertex graph that admits the largest number of r -edge-colorings for which there is no triangle whose edges are assigned three distinct colors. Moreover, we extend this result to lower values of n when r ≥ 10 , and we provide approximate results for r ∈ { 3 , 4 } .

Basic definitions are given in the next paragraph. We study second clique graphs of suspensions of graphs, K 2 ( S ( G ) ) , and characterize them, in terms of an auxiliary biclique operator B which transforms a graph G into its biclique graph B(G). The characterization is then: K 2 ( S ( G ) ) ≅ B ( K ( G ) ) . We found a characterization of the graphs, G, that maximize | B ( G ) | for any given order n = | G | . This particular version of a biclique operator is new in the literature. The main motivation to study B(G) is an attempt to characterize the graphs G that maximize | K 2 ( G ) | , thus mimicking a result of Moon and Moser [12] that characterizes the graphs maximizing | K ( G ) | . The clique graph K(G) of a a graph G is the intersection graph of the set of all (maximal) cliques of G (and K 2 ( G ) = K ( K ( G ) ) ). The suspension S(G) of a graph G is the graph obtained from G by adding two new vertices which are adjacent to all other vertices, but not to each other. Here, a biclique (X, Y ) is an ordered pair of not necessarily disjoint subsets of vertices of G such that each x ∈ X is adjacent or equal to every y ∈ Y and such that (X, Y ) is maximal under component-wise inclusion. Finally B(G) is the graph whose vertices are the bicliques of G with adjacencies given by ( X , Y ) ≃ ( X ′ , Y ′ ) if and only if X ∩ X ′ ≠ ∅ or Y ∩ Y ′ ≠ ∅ .

We consider only connected bipartite graphs G with a unique perfect matching M . Let G w be the weighted graph obtained from G by giving weights to its edges using the positive weight function w : E ( G ) → ( 0 , ∞ ) such that w ( e ) = 1 for each e ∈ M . An unweighted graph G may be viewed as a weighted graph with the weight function w ≡ 1 . A weighted graph G w is nonsingular if its adjacency matrix A ( G w ) is nonsingular. The inverse of a nonsingular weighted graph G w is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G w ) via a diagonal matrix of ±1s. By G / M we denote the graph obtained from G by contracting each edge of M to a single vertex. It is known that if G / M is bipartite, then G w is invertible for each weight function w. In this article, we consider the converse of this result and show that if G w is invertible for each w, then the graph G / M is bipartite. We also supply exact conditions under which G w is invertible for one w will force that the graph G / M is bipartite.

Let D 2 n denote the dihedral group of order 2 n , where n ≥ 3 . In this article, we build upon the findings of Haggard and McCarthy who, for certain values of n , produced a vertex-minimal graph with dihedral symmetry. Specifically, Haggard considered the situation when n 2 or n is a prime power, and McCarthy investigated the case when n is not divisible by 2 , 3 or 5 . In this article, we assume n is not divisible by 4 and construct a vertex-minimal graph whose automorphism group is isomorphic to D 2 n .

A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order 9 p for each prime p .

Let G = ( V , E ) be a simple graph of order n. The normalized Laplacian eigenvalues of graph G are denoted by ρ 1 ( G ) ≥ ρ 2 ( G ) ≥ ⋯ ≥ ρ n − 1 ( G ) ≥ ρ n ( G ) = 0 . Also let G and G ′ be two nonisomorphic graphs on n vertices. Define the distance between the normalized Laplacian spectra of G and G ′ as σ N ( G , G ′ ) = ∑ i = 1 n | ρ i ( G ) − ρ i ( G ′ ) | p , p ≥ 1 . Define the cospectrality of G by c s N ( G ) = min ⁡ { σ N ( G , G ′ ) : G ′ not isomorphic to G } . Let c s n N = max ⁡ { c s N ( G ) : G a graph on n vertices } . In this paper, we give an upper bound on c s N ( G ) in terms of the graph parameters. Moreover, we obtain an exact value of c s n N . An upper bound on the distance between the normalized Laplacian spectra of two graphs has been presented in terms of Randic energy. As an application, we determine the class of graphs, which are lying closer to the complete bipartite graph than to the complete graph regarding the distance of normalized Laplacian spectra.

The connective eccentricity index is a novel graph invariant with vast potential in structure activity/property relationships. This graph invariant displays high discriminating power with respect to both biological activity and physical properties. Given a simple connected graph G, the connective eccentricity index (CEI) of G is defined as ξ e e ( G ) = ∑ u v ∈ E G ( 1 e G ( u ) + 1 e G ( v ) ) , where e G ( ⋅ ) denotes the eccentricity of the corresponding vertex. In this paper, we first determine the sharp upper bound on the CEI of graphs in the class of all n-vertex connected bipartite graphs with matching number q, the maximum CEI is realized only by the graph K q , n − q . Second, we characterize the graph with the maximum CEI in the class of all the n-vertex connected bipartite graphs of given diameter. Finally, all the extremal graphs having the maximum CEI in the class of all the connected n-vertex bipartite graphs with a given connectivity s are identified as well.

A Gray code of length n is a list of all binary words of length n such that each two successive codewords differ in only one bit position. If the first and the last codewords also share this property, the Gray code is called cyclic, otherwise it is called non-cyclic. The numbers indicating bit positions in where two successive codewords differ in the list of Gray codes are called transition numbers, and the sequence of these all numbers is called the transition sequence of the Gray code. In this article, bit positions of a Gray code of length n will be counted from 1 up until n. If a graph with vertex set {1, 2, ..., n} having the property that two vertices i and j are adjacent in the graph if and only if, i and j are consecutive transitions in the transition sequence of a Gray code, then the graph is called induced by the Gray code. Some classes of bipartite graphs are shown to be induced by Gray codes. Particularly, we show that complete bipartite graphs are induced by Gray codes.

A graph is called symmetric if its automorphism group is transitive on its arcs. In this paper, we classify symmetric graphs of order four times an odd square-free integer and valency seven. It is shown that, either the graph is isomorphic to one of 9 specific graphs or its full automorphism group is isomorphic to PSL ( 2 , p ) , PGL ( 2 , p ) , PSL ( 2 , p ) × Z 2 or PGL ( 2 , p ) × Z 2 with p ≡ ± 1 ( mod 7 ) a prime.

The prime graph question asks whether the Gruenberg–Kegel graph of an integral group ring [Formula: see text], i.e. the prime graph of the normalized unit group of [Formula: see text], coincides with that one of the group [Formula: see text]. In this note, we prove for finite groups [Formula: see text] a reduction of the prime graph question to almost simple groups. We apply this reduction to finite groups [Formula: see text] whose order is divisible by at most three primes and show that the Gruenberg–Kegel graph of such groups coincides with the prime graph of [Formula: see text].

We give a polynomial-time algorithm to decide whether a connected bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of disjoint edges cross. We consider the problem of deciding whether there exists such a drawing in which a specified subset of triples of pairwise crossing edges are concurrent. We give a necessary condition for the same and conjecture that it is sufficient.

We show that for any e > 0 , and any integer k ≥ 2 , there is a C 2 k -free graph G which does not contain a bipartite subgraph of girth greater than 2k with more than ( 1 − 1 2 2 k − 2 ) 2 2 k − 1 ( 1 + e ) fraction of the edges of G. Győri et al. showed that if c denotes the largest constant such that every C 6 -free graph G contains a bipartite subgraph which is C 4 -free having c fraction of edges of G, then 3 8 ≤ c ≤ 2 5 . Putting k = 3, our result implies that c = 3 8 . Our proof uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdős: For any e > 0 , and any integers a , b , k ≥ 2 , there exists an a-uniform hypergraph H of girth greater than k which does not contain any b-colorable subhypergraph with more than ( 1 − 1 b a − 1 ) ( 1 + e ) fraction of the hyperedges of H. Kuhn and Osthus showed that every bipartite C 2 l -free graph G contains a C 4 -free subgraph with at least 1 / ( l − 1 ) fraction of the edges of G. We give a new and simple proof of this result. In the same paper Kuhn and Osthus also showed that a C 2 l -free graph which is obtained by pasting together C 4 's has average degree at most 16l and asked whether there exists a number d = d ( l ) such that every C 2 l -free graph which is obtained by pasting together C 2 k 's has average degree at most d if l > k ≥ 3 are given integers. We answer this question negatively.

A graph with a cyclic group of automorphisms acting semiregularly on the vertices with two orbits is called a bi-circulant. A graph is half-arc-transitive if it is both vertex-transitive and edge-transitive but not arc-transitive. Then we say that a half-arc-transitive graph is half-arc-regular if its full automorphism group acts regularly on its edges. It is known that the smallest possible valency of a half-arc-transitive bi-circulant is 6 . In this paper, a classification is given of connected half-arc-regular bi-circulants of valency 6 . As byproduct, we construct the first known infinite family of half-arc-transitive bi-circulants of valency 6 .

A graph is said to be a bi-Cayley graph over a group H if it admits H as a semiregular automorphism group with two vertex-orbits. A bi-dihedrant is a bi-Cayley graph over a dihedral group. In this paper, it is shown that every connected trivalent edge-transitive bi-dihedrant is also vertex-transitive, and then we present a classification of trivalent arc-transitive bi-dihedrants, and study the Cayley property of trivalent vertex-transitive bi-dihedrants.

A P l -decomposition of a graph G is a set of edge-disjoint copies of P l in G that cover the edge set of G, where P l is the path with l edges. Kouider and Lonc [M. Kouider, Z. Lonc, Path decompositions and perfect path double covers, Australas. J. Combin. 19 (1999) 261–274] conjectured that any 2l-regular graph G admits a P l -decomposition D where every vertex of G is the end-vertex of exactly two paths of D. In this paper we verify Kouider and Lonc's Conjecture for paths of length 4.

In this paper, the orthogonal graph of type ( m , m − 1 , 0 ) over F q of odd characteristic is introduced. We study the elementary properties of the graph and show that the first subconstituent of it is a generalized strongly regular graph. Moreover, the structure of the second subconstituent and the adjacency relations between different subconstituents are given.

The strong chromatic index of a graph G, denoted by s(G), is the minimum possible number of colors in a coloring of the edges of G such that each color class is an induced matching. The corresponding fractional parameter is denoted by sf(G).For a bipartite graph G we have sf(G)1.5G2. This follows as an easy consequence of earlier results the fractional variant of Reeds conjecture and the theorem by Faudree, Gyrfs, Schelp and Tuza from 1990. Both these results are tight so it may seem that the bound 1.5G2 is best possible.We break this 1.5 barrier. We prove that sf(G)1.4762G2+G1.5 for every bipartite graph G. The main part of the proof is a structural lemma regarding cliques in L(G)2.

Labelings that are used in graph decompositions are called Rosa-type labelings. The gamma-labeling of an almost-bipartite graph is a natural generalization of an alpha-labeling of a bipartite graph. It is known that if a bipartite graph G with m edges possesses an alpha-labeling or an almost-bipartite graph G with m edges possesses a gamma-labeling, then the complete graph K_{2mx+1} admits a cyclic G-decomposition. A variation of an alpha-labeling is introduced in this paper by allowing additional vertex labels and some conditions on edge labels and show that whenever a bipartite graph G admits such a labeling, then there exists a supergraph H of G such that H is almost-bipartite and H has a gamma-labeling.

In 2008, it is shown that if HK1,3 (the claw), then every H-free graph G has an even factor if and only if (G)2 and every odd branch-bond of G having an edge-branch. In this paper, we characterize all connected graphs H with order at least three such that every H-free graph has an even factor if and only if (G)2 and every odd branch-bond of G has an edge-branch.

If G is any graph, the prism graph of G, denoted P(G), is the cartesian product of G with a single edge, or equivalently, the graph obtained by taking two copies of G, say G1 and G2, with the same vertex labelings and joining each vertex of G1 to the vertex of G2 having the same label by an edge. A connected graph G has property E(m,n) (or more briefly G is E(m,n)) if for every pair of disjoint matchings M and N in G with |M|=m and |N|=n respectively, there is a perfect matching F in G such that MF and NF=. A graph which has the E(m,0) property is also said to be m-extendable. In this paper, we begin the study of the E(m,n) properties of the prism graph P(G) when G is an arbitrary graph as well as the more special situations when, in addition, G is bipartite or bicritical.

The power graph $\mathcal{P}(G)$ of a group $G$ is the graphwith group elements as vertex set and two elements areadjacent if one is a power of the other. The aim of this paper is to compute the automorphism group of the power graph of several well-known and important classes of finite groups.

Many important graphs are bipartite and cubic (i.e. bipartite and trivalent, or “bicubic”). We explain concisely how the Hamilton cycles of this type of graph are characterized by a single determinantal condition over GF ( 2 ) . Thus algebra may be used to derive results such as those of Bosak, Kotzig, and Tutte that were originally proved differently.

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, a complete classification of connected pentavalent symmetric graphs of order 16p is given for each prime p. It follows from this result that a connected pentavalent symmetric graph of order 16p exists if and only if p = 2 or 31, and that up to isomorphism, there are three such graphs.

For a finite group G , the power graph P ( G ) is a graph with the vertex set G , in which two distinct elements are adjacent if one is a power of the other. Feng, Ma and Wang (Feng et al., 2016) described the full automorphism group of P ( G ) . In this paper, we study automorphism groups of the main supergraphs and cyclic graphs, which are supergraphs of P ( G ) . It is proved that the automorphism group of these graphs can be written as a combination of Cartesian and wreath products of some symmetric groups. The full automorphism groups of these graphs of certain finite groups are also calculated.

In this article we deal with the sign of ?2 - r, r > 0, where ?2 is the second largest eigenvalue of (adjacency matrix of) a simple graph and present some methods of determining it for some classes of graphs. The main result is a set of graph mappings that preserve the value of sgn (?2 - r). These mappings induce equivalence relations among involved graphs, thus providing a way to indirectly apply the GRS-theorem (the generalization of so-called RS-theorem) to some GRS-undecidable (or RS-undecidable) graphs. To present possible applications, we revisit some of the previous results for reexive graphs (graphs whose second largest eigenvalue does not exceed 2). We show how maximal reexive graphs that belong to various families depending on their cyclic structure, can be reduced to RS-decidable graphs in terms of corresponding equivalence relations.

The non-commuting graph Γ(G) of group G is a graph with the vertex set G − Z(G) and two distinct vertices x and y are adjacent whenever xy = yx. In this paper, we compute the spectrum of non-commuting graphs of some wellknown groups. Further, if G is a non-abelian finite group and its non-commuting graph Γ(G) is k−regular, then we prove k = 2sq where q is an odd prime.

A connected graph whose automorphism group acts transitively on the edges and vertices, but not on the set of ordered pairs of adjacent vertices of the graph is called half-arc-transitive. It is well known that the valence of a half-arc-transitive graph is even and at least four. Several infinite families of half-arc-transitive graphs of valence four are known, however, in all except four of the known specimens, the vertex-stabiliser in the automorphism group is abelian. The first example of a half-arc-transitive graph of valence four and with a non-abelian vertex-stabiliser was described in Conder and Marusic (2003) 4. This example has 10752 vertices and vertex-stabiliser isomorphic to the dihedral group of order 8. In this paper, we show that no such graphs of smaller order exist, thus answering a frequently asked question.