Search

We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $\mathcal{C}$ one can find tw...

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path receive the same color. For a connected graph G, the proper connection number p c ( G ) of G is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of G is connected by at least one proper path in G. Recently, Li and Magnant in [8] posed the following conjecture: If G is a connected noncomplete graph of order n ≥ 5 and minimum degree δ ( G ) ≥ n / 4 , then p c ( G ) = 2 . In this paper, we show that this conjecture is true except for two small graphs on 7 and 8 vertices, respectively. As a byproduct we obtain that if G is a connected bipartite graph of order n ≥ 4 with δ ( G ) ≥ n + 6 8 , then p c ( G ) = 2 .

Komlos [Tiling Turan theorems, Combinatorica, 20,2 (2000), 203{218] determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree., Comment: 13 pages, 1 figure, accepted to the European Journal of Combinatorics

The classical Dirac theorem asserts that every graph G on n ≥ 3 vertices with minimum degree δ ( G ) ≥ ⌈ n ∕ 2 ⌉ is Hamiltonian. The lower bound of ⌈ n ∕ 2 ⌉ on the minimum degree of a graph is tight. In this paper, we extend the classical Dirac theorem to the case where δ ( G ) ≥ ⌊ n ∕ 2 ⌋ by identifying the only non-Hamiltonian graph families in this case. We first present a short and simple proof. We then provide an alternative proof that is constructive and self-contained. Consequently, we provide a polynomial-time algorithm that constructs a Hamiltonian cycle, if exists, of a graph G with δ ( G ) ≥ ⌊ n ∕ 2 ⌋ , or determines that the graph is non-Hamiltonian. Finally, we present a self-contained proof for our algorithm which provides insight into the structure of Hamiltonian cycles when δ ( G ) ≥ ⌊ n ∕ 2 ⌋ and is promising for extending the results of this paper to the cases with smaller degree bounds.

For a graph G, with v as any vertex, the maximum distance of v to another vertex or node is defined as the eccentricity \(e\left( v \right)\) of the vertex v. Of all the eccentricities, the minimum is the radius, maximum of the eccentricities is the diameter, of graph G. If the eccentricity of any vertex is equal to the radius, then the vertex is said to be the central vertex of G. So, if for G, every vertex is the center, then G is defined as a graph that is self-centered. Here, we construct and characterize the power graph of any self-centered graph having a regular eccentric sequence. Also, the embedding of special graphs is discussed here.

A graph G(V,E) is a structure used to model pairwise relations between a set of objects. In this context, a graph is a collection of vertices (representing the objects) and a collection of edges (representing the relation) that connect pairs of vertices. It is possible to represent a graph using an adjacency matrix, but often this is not the most efficient representation of the relation. In studying graph representation, the object is to capture the structure of the graph more efficiently using a variety of other discrete structures. This work considers path representations of graphs. Consider a host graph, H. A path representation [H : r : q] of a target graph G is a labeling in which each vertex is assigned a unique path of length r found in H in such a way that if uv ∈ E(G), then the Pr assigned to u and the Pr assigned to v have at least a Pq in common. This study considers representations in which the host tree is the complete graph on n vertices, [Kn, r, q] which will be referred to as Pr,q-representations. This work also considers the area in graph theory known as vertex-coloring, specifically coloring planar graphs, and explores a special class of planar graphs called “coils”.

Golumbic and Trenk first introduced tolerance graph [7] to generalize some well-known applications of interval graphs. In a tolerance graph, every vertex is represented by an interval and a tolerance such that an edge occurs if and only if the overlap of corresponding intervals is at least as large as the tolerance associated with one of the vertices. Resource allocation sharing tolerate among users and certain scheduling problems can be modeled by tolerance graphs.

Recently, people, devices, processes, and other entities have been more connected than at any other point in history. In general, a graph is a natural, neat, and flexible structure to model the complex relationships, interactions, and interdependencies between objects (Fig. 4.1). In particular, each graph consists of nodes (or vertices) that represent objects and edges (or links) that represent the relationships among the graph nodes. Graphs have been widely used to represent datasets in a wide range of application domains such as social science, astronomy, computational biology, telecommunications, computer networks, semantic Web, protein networks, and many others (Sakr and Pardede, Graph Data Management: Techniques and Applications, 2011 [73]).

Let G be a graph embedded in a surface of nonnegative characteristic with maximum degree $$\varDelta $$ . The entire chromatic number $$\chi _\mathrm{vef}$$ of G is the least number of colors such that any two adjacent or incident elements in $$V(G)\cup E(G) \cup F(G)$$ have different colors. In this paper, we prove that $$\chi _\mathrm{vef}(G)\le \varDelta +4$$ if $$\varDelta \ge 6$$ , and $$\chi _\mathrm{vef}(G)\le \varDelta +5$$ if $$\varDelta \le 5$$ .

Correspondence problems are challenging due to the complexity of real-world scenes. One way to solve this problem is to improve the graph matching (GM) process, which is flexible for matching non-rigid objects. GM can be classified into three categories that correspond with the variety of object functions: first-order, second-order, and high-order matching. Graph and hypergraph matching have been proposed separately in previous works. The former is equivalent to the second-order GM, and the latter is equivalent to high-order GM, but we use the terms second- and high-order GM to unify the terminology in this paper. Second- and high-order GM fit well with different types of problems; the key goal for these processes is to find better-optimized algorithms. Because the optimal problems for second- and high-order GM are different, we propose two novel optimized algorithms for them in this paper. (1) For the second-order GM, we first introduce a $K$ -nearest-neighbor-pooling matching method that integrates feature pooling into GM and reduces the complexity. Meanwhile, we evaluate each matching candidate using discriminative weights on its $k$ -nearest neighbors by taking locality as well as sparsity into consideration. (2) High-order GM introduces numerous outliers, because precision is rarely considered in related methods. Therefore, we propose a sub-pattern structure to construct a robust high-order GM method that better integrates geometric information. To narrow the search space and solve the optimization problem, a new prior strategy and a cell-algorithm-based Markov Chain Monte Carlo framework are proposed. In addition, experiments demonstrate the robustness and improvements of these algorithms with respect to matching accuracy compared with other state-of-the-art algorithms.

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n4)-time solvable for graphs of maximum degree at most 6.

The Turan number ex ( n , H ) is the maximum number of edges in a graph on n vertices which does not contain H as a subgraph. Gorgol gives a lower bound for ex ( n , H ) when H is the disjoint union of k copies of P 3 and conjectures this bound is tight. In this paper, we give an algorithmic proof of Gorgol’s Conjecture.

A caterpillar is a connected graph such that the removal of all its vertices with degree 1 results in a path. Given a graph G , a caterpillar-packing of G is a set of vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by F. Rinaldi and A. Franz in 2007. We study the polytope associated with a natural integer programming formulation of this problem. We explore basic properties of this polytope, including a lifting lemma and several facet-preserving operations on the graph. These results allow us to introduce several families of facet-inducing inequalities.

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.

The Kite graph $Kite_{p}^{q}$ is obtained by appending the complete graph $K_{p}$ to a pendant vertex of the path $P_{q}$. In this paper, the kite graph is proved to be determined by the spectrum of its adjacency matrix., 14 pages, 7 figures

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. We study numerous problems on split graphs, namely the k -Vertex-Disjoint Paths , k -Cycle , k -Path and k - l -Stable Set problems. In the k -Vertex-Disjoint Paths problem, we are given a graph and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k -Cycle / k -Path problem, we are given a graph and are asked whether there is a path/cycle of length k . The k - l -Stable Set problem takes a graph and an integer k as input, and asks whether the graph has a subset of k vertices such that the distance between every two vertices in the subset is at least l + 1 . It is known that all the above problems are NP-complete on split graphs. We derive a 4 k -vertex kernel for the k -Vertex-Disjoint Paths problem and an O ( k 2 ) -vertex kernel for both the k -Path problem and the k -Cycle problem. Concerning the k - l -Stable Set problem, for l = 1 or l ≥ 3 , the problem is polynomial-time solvable on split graphs. For l = 2 , we prove that the k - l -Stable Set problem is W[1]-complete on split graphs, with respect to k . However, if the given split graph contains no K 1 , r as an induced subgraph, and every vertex in the independent set of the split graph has degree at most d , we derive a linear vertex kernel for the k - 2 -Stable Set problem, where both r and d are constants.

A strong edge coloring of a graph is a proper edge coloring in which every color class is an induced matching. The strong chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors in a strong edge coloring of $G$. Let $\Delta \geq 4$ be an integer. In this note, we study the odd graphs and show the existence of some special walks. By using these results and Chang's ideas in [Discuss. Math. Graph Theory 34 (4) (2014) 723--733], we show that every planar graph with maximum degree at most $\Delta$ and girth at least $10 \Delta - 4$ has a strong edge coloring with $2\Delta - 1$ colors. In addition, we prove that if $G$ is a graph with girth at least $2\Delta - 1$ and mad$(G) < 2 + \frac{1}{3\Delta - 2}$, where $\Delta$ is the maximum degree and $\Delta \geq 4$, then $\chi_s'(G) \leq 2\Delta - 1$, if $G$ is a subcubic graph with girth at least $8$ and mad$(G) < 2 + \frac{2}{23}$, then $\chi_s'(G) \leq 5$., Comment: 7 pages

A simple graph-product type construction shows that for all natural numbers r≥q, there exists an edge-coloring of the complete graph on 2r vertices using r colors where the graph consisting of the union of any q color classes has chromatic number 2q. We show that for each fixed natural number q, if there exists an edge-coloring of the complete graph on n vertices using r colors where the graph consisting of the union of any q color classes has chromatic number at most 2q − 1, then n must be sub-exponential in r. This answers a question of Conlon, Fox, Lee, and Sudakov.

Let k be a positive integer. In this paper, we prove that for a graph G with at least 4 k vertices, if max { d ( x ) , d ( y ) } ≥ 2 k for any pair of nonadjacent vertices { x , y } ⊆ V ( G ) , then G contains k disjoint cycles. This generalizes the results given by Corra di and Hajnal (1963), Enomoto (1998), and Wang (1999).

Let G be a finite simple undirected graph with n vertices and m edges. The energy of a graph G , denoted by E ( G ) , is defined as the sum of the absolute values of the eigenvalues of G . In this paper we present lower bounds for E ( G ) in terms of number of vertices, edges, Randić index, minimum degree, diameter, walk and determinant of the adjacency matrix. Also we show our lower bound in (11) under certain conditions is better than the classical bounds given in Caporossi et al. (1999), Das (2013) and McClelland (1971). Keywords: Energy (of non-singular graph), Determinant of adjacency matrix, Randić index, Spectral radius

Sharp bounds on some distance-based graph invariants of $n$-vertex $k$-trees are established in a unified approach, which may be viewed as the weighted Wiener index or weighted Harary index. The main techniques used in this paper are graph transformations and mathematical induction. Our results demonstrate that among $k$-trees with $n$ vertices the extremal graphs with the maximal and the second maximal reciprocal sum-degree distance are coincident with graphs having the maximal and the second maximal reciprocal product-degree distance (and similarly, the extremal graphs with the minimal and the second minimal degree distance are coincident with graphs having the minimal and the second minimal eccentricity distance sum).

Using a single commodity computational node to partition big graph is very difficult. This work studies how to partition a big graph with respect to arbitrary proportions in a streaming manner. To meet diverse requirements of big graph partitioning scenarios, we first devise 3 measurement schemes for measuring the graph vertex count, graph workload, and graph processing time, respectively. These schemes are the bases and prerequisites for big graph partitioning. Due to the difficulty in acquiring full big graph information, we then design 8 streaming heuristics to partitioning a big graph during the process of loading its data from external disks into memory. Each of these heuristics decides where to assign every vertex in the stream based on the information calculated by one of the above 3 schemes. At last, we demonstrate the performance and flexibility of our heuristics in partitioning real and synthetic graph datasets on a medium-sized cluster. The characteristics of arbitrary proportions of our approach makes it have a wide range of applications.

The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform edit costs and incorporates information about both node and edge labels. In this paper, we demonstrate that this algorithm is incorrect. We present a corrected version $\mathsf {B\scriptstyle{RANCH}}$ that runs in $\mathcal{O}(n^2\Delta ^3+n^3)$ time, where $\Delta$ is the maximum of the maximum degrees of input graphs $G$ and $H$ . We also develop a speed-up $\mathsf {B\scriptstyle{RANCH}}\mathsf{F\scriptstyle{AST}}$ that runs in $\mathcal{O}(n^2\Delta ^2+n^3)$ time and computes an only slightly less accurate lower bound. The lower bounds produced by $\mathsf {B\scriptstyle{RANCH}}$ and $\mathsf {B\scriptstyle{RANCH}}\mathsf{F\scriptstyle{AST}}$ are shown to be pseudo-metrics on a collection of graphs. Finally, we suggest an anytime algorithm $\mathsf {B\scriptstyle{RANCH}}\mathsf{T\scriptstyle{IGHT}}$ that iteratively improves $\mathsf {B\scriptstyle{RANCH}}$ ’s lower bound. $\mathsf {B\scriptstyle{RANCH}}\mathsf{T\scriptstyle{IGHT}}$ runs in $\mathcal{O}(n^3\Delta ^2+I(n^2\Delta ^3+n^3))$ time, where the number of iterations $I$ is controlled by the user. A detailed experimental evaluation shows that all suggested algorithms are Pareto optimal, that they are very effective when used as filters for edit distance range queries, and that they perform excellently when used within classification frameworks.

The k-triangle graph Tk(G) is obtained from a graph G by replacing each edge in G with k + 1 parallel paths, in which one is of length 1 and each of the rest k paths is of length 2; whereas the k-quadrilateral graph Qk(G) is obtained from G by replacing each edge in G with k + 1 parallel paths, in which one is of length 1 and each of the rest k paths is of length 3. In this paper, we completely determine the normalized Laplacian spectrum on Tk(G) (resp. Qk(G)) for any connected graph G, k ⩾ 2. As applications, the correlation between the degree-Kirchhoff index, the Kemeny’s constant and the number of spanning trees of Tk(G) (resp. Qk(G), the r-th iterative k-triangle graph T r k ( G ) , the r-th iterative k-quadrilateral graph Q r k ( G ) ) and those of G are derived. Our results extend those main results obtained in Xie et al. (2016) and Li and Hou (2017).

The irregularity of a simple graph G = ( V , E ) is defined as irr ( G ) = ∑ u v ∈ E ( G ) | d G ( u ) − d G ( v ) | , where dG(u) denotes the degree of a vertex u ∈ V(G). This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. Recently, it also gains interest in Chemical Graph Theory, where it is named the third Zagreb index. In this paper, by means of the Laplacian eigenvalues and the normalized Laplacian eigenvalues of G, we establish some new spectral upper bounds for irr(G). We then compare these new bounds with a known bound by Goldberg, and it turns out that our bounds are better than the Goldberg bound in most cases. We also present two spectral lower bounds on irr(G).

We study the local k-coloring of graphs.We prove that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3.We prove that it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8. A local k-coloring of a graph G is a function f:V(G){1,2,,k} such that for each SV(G), 2|S|3, there exist u,vS with |f(u)f(v)| at least the size of the subgraph induced by S. The local chromatic number of G is (G)=min{k:Ghas a localk-coloring}. In this paper, we show that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3. In particular, it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8.

A graph G = ( V , E ) is C probe if V can be partitioned into two sets, probes P and non-probes N , where N is independent and new edges may be added between non-probes such that the resulting graph is in the graph class C . We say that ( N , P ) is a C probe partition for G . The C partitioned probe problem consists of an input graph G with a vertex partition ( N , P ) and the question: Is ( N , P ) a C probe partition for G ? A ( k , l ) -partition of a graph G is a partition of its vertex set into at most k independent sets and l cliques. A graph is ( k , l ) if it has a ( k , l ) -partition. We prove that the C partitioned probe problem is polynomial for (1,2) and for (2,1)-graphs, and NP-complete for (2,2)-graphs. The results give the first graph class for which the partitioned probe problem is NP-complete, and the full complexity dichotomy into NP-complete and polynomial for ( k , l ) partitioned probe problems: they are NP-complete if k 2 + l 2 ≥ 8 , and polynomial otherwise.

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 .

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph.

The vertices of Kneser graph K ( n , k ) are the subsets of { 1 , 2 , … , n } of cardinality k , two vertices are adjacent if and only if they are disjoint. The square G 2 of a graph G is defined on the vertex set of G with two vertices adjacent if their distance in G is at most 2. Z. Furedi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when n = 2 k + 1 . It is believed that χ ( K 2 ( 2 k + 1 , k ) ) = 2 k + c where c is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: 8 k ∕ 3 + 20 ∕ 3 for 1 k ≥ 3 (Kim and Park, 2014) and 32 k ∕ 15 + 32 for k ≥ 7 (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to χ ( K 2 ( 2 k + 1 , k ) ) ≤ 5 k ∕ 2 + c , where c is a constant in { 5 ∕ 2 , 9 ∕ 2 , 5 , 6 } , depending on k ≥ 2 .

The Jevons group is the exponential group S2 t Sn. It is generated by the group of all permutation (n x n)-matrices over GF(2) and the translation group on the n-dimensional vector space Vn over GF(2). For a permutation group G on Vn being an overgraph of S2 t Sn, an orbital of G is an orbit of G in its natural action on Vn x Vn. The orbital graph associated with an orbital Г is the graph with the vertex set Vn and the edge set Г. In this paper, we classify distance-transitive orbital graphs of overgroups of the Jevons group S2 t Sn and show that some of them are isomorphic to the following graphs: the complete graph K2n, the complete bipartite graph K2n-i,2n-i, the halved (n + 1)-cube, the folded (n + 1)-cube, alternating forms graphs, the Taylor graph, the Hadamard graph.

Graph polynomials are deemed useful if they give rise to algebraic characterizations of various graph properties, and their evaluations encode many other graph invariants. Algebraic: The complete graphs K n and the complete bipartite graphs K n , n can be characterized as those graphs whose matching polynomials satisfy a certain recurrence relations and are related to the Hermite and Laguerre polynomials. An encoded graph invariant: The absolute value of the chromatic polynomial χ ( G , X ) of a graph G evaluated at − 1 counts the number of acyclic orientations of G . In this paper we prove a general theorem on graph families which are characterized by families of polynomials satisfying linear recurrence relations. This gives infinitely many instances similar to the characterization of K n , n . We also show where to use, instead of the Hermite and Laguerre polynomials, linear recurrence relations where the coefficients do not depend on n . Finally, we discuss the distinctive power of graph polynomials in specific form.