Search

Let H be a subgraph of graph G. If the edge set of G can be partitioned into edge-disjoint copies of H, possibly with some remainder edges, then the partition is called an H-packing in G. A maximal H-packing in G is defined as one where the remainder edges do not contain any copies of H. A maximal H-packing of G is considered maximum if the edge set E(G) cannot be partitioned into an H-packing containing more copies of H. A graph G is referred to as being H-equipackable if every maximal H-packing in G is also maximum H-packing. In this paper, we provide a characterization for all P 3 ∪ P 2 -equipackable graphs with 3 m (m ≥ 1) edges, where P 3 ∪ P 2 represents the union of two disjoint paths with 3 vertices and 2 vertices. [ABSTRACT FROM AUTHOR]

Robin Forman’s highly influential 2002 paper A User’s Guide to Discrete Morse Theory presents an overview of the subject in a very readable manner. As a proof of concept, the author determines the topology (homotopy type) of the abstract simplicial complex of disconnected graphs of order n (which was previously done by Victor Vassiliev using classical topological methods) using discrete Morse theoretic techniques, which are purely combinatorial in nature. The techniques involve the construction (and verification) of a discrete gradient vector field on the complex. However, the verification part relies on a claim that does not seem to hold. In this note, we provide a couple of counterexamples against this specific claim. We also provide an alternative proof of the bigger claim that the constructed discrete vector field is indeed a gradient vector field. Our proof technique relies on a key observation which is not specific to the problem at hand, and thus is applicable while verifying a constructed discrete vector field is a gradient one in general.

The crossing number of a graph G, c r (G) , is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. There are almost no results concerning crossing number of join of a disconnected 6-vertex graph with cycle. The main aim of this paper is to give the crossing number of the join product Q + C n for the disconnected 6-vertex graph Q consisting of the two 3-cycles, where C n is the cycle on n vertices. [ABSTRACT FROM AUTHOR]

Let \(G\) be an undirected simple graph on n vertices and \(\sigma^2(G)=n-2\) (degree sum of any two non-adjacent vertices in \(G\) is equal to \(n-2\)) and \(\alpha(G)\) be the cardinality of an maximum independent set of \(G\). In \(G\), a vertex of degree \((n-1)\) is called total vertex. We show that, for \(n\geq3\) is an odd number then \(\alpha(G)=2\) and \(G\) is a disconnected graph; for \(n\geq4\) is an even number then \(2\leq\alpha(G)\leq(n+2)/2\), where if \(\alpha(G)=2\) then \(G\) is a disconnected graph, otherwise \(G\) is a connected graph, \(G\) contains \(k\) total vertices and \(n-k\) vertices of degree \(\delta=(n-2)/2\), where \(0\leq k\leq(n-2)/2\). In particular, when \(k=0\) then \(G\) is an \((n-2)/2\)-Regular graph.

For any (not necessary connected) graph $G(V,E)$ and $A\subseteq V(G)$, the distance of a vertex $x\in V(G)$ and $A$ is $d(x,A)=\min\{d(x,a): a\in A\}$. A subset of vertices $A$ resolves two vertices $x,y \in V(G)$ if $d(x,A)\neq d(y,A)$. For an ordered partition $\Lambda=\{A_1, A_2,\ldots, A_k\}$ of $V(G)$, if all $d(x,A_i)\infty$ for all $x\in V(G)$, then the representation of $x$ under $\Lambda$ is $r(x|\Lambda)=(d(x,A_1), d(x,A_2), \ldots, d(x,A_k))$. Such a partition $\Lambda$ is a resolving partition of $G$ if every two distinct vertices $x,y\in V(G)$ are resolved by $A_i$ for some $i\in [1,k]$. The smallest cardinality of a resolving partition $\Lambda$ is called a partition dimension of $G$ and denoted by $pd(G)$ or $pdd(G)$ for connected or disconnected $G$, respectively. If $G$ have no resolving partition, then $pdd(G)=\infty$. In this paper, we studied the partition dimension of disjoint union of complete bipartite graph, namely $tK_{m,n}$ where $t\geq 1$ and $m\geq n\geq 2$. We gave the necessary condition such that the partition dimension of $tK_{m,n}$ are finite. Furthermore, we also derived the necessary and sufficient conditions such that $pdd(tK_{m,n})$ is either equal to $m$ or $m+1$.

Let ℋ be a set of graphs. A graph G is said to be ℋ‐free if G does not contain H as an induced subgraph for all H in ℋ, and we call ℋ a forbidden pair if ∣ℋ∣=2. In 2008, Faudree et al. characterized all pairs of connected graphs R,S such that every 2‐connected {R,S}‐free graph of sufficiently large order has a 2‐factor. In 2013, Fujisawa et al. characterized all pairs of connected graphs R,S such that every connected {R,S}‐free graph of sufficiently large order with minimum degree at least two has a 2‐factor. In this paper, we generalize these two results by considering disconnected graphs R,S. In other words, we characterize all pairs of graphs R,S such that every 2‐connected {R,S}‐free graph of sufficiently large order has a 2‐factor. We also characterize all pairs of graphs R,S such that every connected {R,S}‐free graph of sufficiently large order with minimum degree at least two has a 2‐factor. [ABSTRACT FROM AUTHOR]

The concept of the size Ramsey number of a graph was in- troduced by Erd¨os, Faudree, Rousseau, and Schelp in 1978. There are some published research papers about the size Ram- sey number, (see [1], [2], [5], [6] and [7]), but there are only a few results about the size Ramsey number for a pair of graphs, see [3]. In this paper, we determine the size Ramsey number for three graphs, namely the size Ramsey number for match- ings versus two small disconnected graphs. [ABSTRACT FROM AUTHOR]

Suppose Γ is a finite simple graph. If D is a dominating set of Γ such that each x ∈ D is contained in the set of vertices of an odd cycle of Γ, then we say that D is an odd dominating set for Γ. For a finite group G, let Δ (G) denote the character graph built on the set of degrees of the irreducible complex characters of G. In this paper, we show that the complement of Δ (G) contains an odd dominating set, if and only if Δ (G) is a disconnected graph with non-bipartite complement. [ABSTRACT FROM AUTHOR]

There are only few results concerning crossing numbers of join of some graphs. In this paper, for some graphs on five vertices, we give the crossing numbers of its join with n isolated vertices.

Let and be finite simple graphs where every edge of belongs to at least one subgraph that is isomorphic to . An --antimagic total labeling of a graph is a bijection such that for all subgraphs isomorphic to , the -weights, form an arithmetic progression where are two fixed integers and is the number of subgraphs of isomorphic to . Moreover, if the vertex set receives the minimum possible labels , then is called a super --antimagic total labeling. In this paper we study super --antimagic total labeling of a disconnected graph, namely .

Computing the crossing number of a graph is NP-hard. In the paper, for a disconnected 6-vertex graph Q = C 5 ∪ K 1 , we obtain the crossing number Z (6 , n) + ⌊ n 2 ⌋ of the graph Q n which is the join product of Q with the discrete graph by introducing the "rotation" method. Moreover, we give crossing numbers for join products of Q with the path and the cycle. Besides, we also get directly crossing numbers for join products of some connected 6-vertex graphs with the path and the cycle, some of which were studied by M. Klešč, D. Kravecová, and J. Petrillová. [ABSTRACT FROM AUTHOR]

Given graphs G and H and a positive integer k, the Gallai–Ramsey number, denoted by g r k (G : H) is defined to be the minimum integer n such that every coloring of K n using at most k colors will contain either a rainbow copy of G or a monochromatic copy of H. We consider this question in the cases where G ∈ { P 4 , P 5 } . In the case where G = P 4 , we completely solve the Gallai–Ramsey question by reducing to the 2-color Ramsey numbers. In the case where G = P 5 , we conjecture that the problem reduces to the 3-color Ramsey numbers and provide several results in support of this conjecture. [ABSTRACT FROM AUTHOR]

In this note we extend the Mulder-Nebeský characterization of the interval function of a connected graph to the disconnected case. One axiom needs to be adapted, but also a new axiom is needed in addition.

For a graph G=(V,E), a partition Ω=\{O_1,O_2,…,O_k \} of the vertex set V is called a resolving partition if every pair of vertices u,v∈V(G) have distinct representations under Ω. The partition dimension of G is the minimum integer k such that G has a resolving k-partition. Many results in determining the partition dimension of graphs have been obtained. However, the known results are limited to connected graphs. In this study, the notion of the partition dimension of a graph is extended so that it can be applied to disconnected graphs as well. Some lower and upper bounds for the partition dimension of a disconnected graph are determined (if they are finite). In this paper, also the partition dimensions for some classes of disconnected graphs are given.

In this work, a conjugacy class graph is represented by Γ and G represents non-abelian metabelian group. Conjugacy class graph of a group is the graph associated with the conjugacy classes of the group. Its vertices are the non-central conjugacy classes of the group, and two distinct vertices are joined by an edge if their cardinalities are not coprime. A group is referred to as metabelian if there exits an abelian normal subgroup in which the factor group is also abelian. It has been proven earlier that 25 non-abelian metabelian groups which have order less than 24, which are considered in this work, exist. In this article, the conjugacy class graphs of non-abelian metabelian groups of order less than 24 are determined as well as examples of some finite groups associated to other graphs are given. [ABSTRACT FROM AUTHOR]

Let F, G, and H be simple graphs. The notation F → (G, H) means that if all the edges of F are arbitrarily colored by red or blue, then there always exists either a red subgraph G or a blue subgraph H. The size Ramsey number of graph G and H, denoted by r̂(G, H) is the smallest integer k such that there is a graph F with k edges satisfying F → (G, H). In this research, we will study a modified size Ramsey number, namely the connected size Ramsey number. In this case, we only consider connected graphs F satisfying the above properties. This connected size Ramsey number of G and H is denoted by rc(G, H). We will derive an upper bound of rc(nK2, H), n ≥ 2 where H is 2Pm or 2K1, t, and find the exact values of rc(nK2, H), for some fixed n. [ABSTRACT FROM AUTHOR]

Abstract In this note we discuss (Gaussian) intrinsic conditional autoregressive (CAR) models for disconnected graphs, with the aim of providing practical guidelines for how these models should be defined, scaled and implemented. We show how these suggestions can be implemented in two examples, on disease mapping. [ABSTRACT FROM AUTHOR]

Neighborhood graph based nonlinear dimensionality reduction algorithms, such as Isomap and LLE, perform well under an assumption that the neighborhood graph is connected. However, for datasets consisting of multiple clusters or lying on multiple manifolds, the neighborhood graphs are often disconnected, or in other words, have multiple connected components. Neighborhood graph based dimensionality reduction techniques cannot recognize both the local and global properties of such datasets. In this paper, a new method, called enhanced neighborhood graph, is proposed to solve the problem. The concept is to add edges to the neighborhood graph adaptively and iteratively until it becomes connected. Nonlinear dimensionality reduction can then be performed based on the enhanced neighborhood graph. As a result, both local and global properties of the data can be exactly recognized. In this study, thorough simulations on synthetic datasets and natural datasets are conducted. The experimental results corroborate that the proposed method provides significant improvements on dimensionality reduction for data with disconnected neighborhood graph. [ABSTRACT FROM AUTHOR]

In this paper, we continue investigating the partition dimension for disconnected graphs. We determine the partition dimension for some classes of disconnected graphs G consisting of two components. If $$G=G_1 \cup G_2$$ , then we give the bounds of the partition dimension of G for $$G_1 = P_n$$ or $$G_1=C_n$$ and also for $$pd(G_1)=pd(G_2)$$ . [ABSTRACT FROM AUTHOR]

Let H be a class of given graphs. A graph G is said to be H -free if G contains no induced copies of H for every H ∈ H . A graph is called traceable if it contains a Hamilton path. Faudree and Gould (1997) characterized all the pairs { R , S } of connected subgraphs such that every connected { R , S } -free graph is traceable. Li and Vrána (2016) first consider the disconnected forbidden subgraphs, and characterized all pairs of disconnected forbidden subgraphs for hamiltonicity. In this article, we characterize all pairs { R , S } of graphs such that there exists an integer n 0 such that every connected { R , S } -free graph of order at least n 0 is traceable. [ABSTRACT FROM AUTHOR]

The problem of reconstructing the characteristic polynomial of a graph of order at least 3 from the collection of characteristic polynomials of its vertex-deleted subgraphs was posed by Cvetković in 1973 as a spectral counter part to the well-known Ulam's reconstruction conjecture. Over the last 50 years, this problem has received notable attention, many positive results have been obtained, but in the general case the problem is still unresolved. In particular, no counter example is found in literature. In this expository paper we survey classical and some more recent results concerning the polynomial reconstruction problem, discuss some related problems, variations and generalizations. [ABSTRACT FROM AUTHOR]

Let H be a given graph. A graph G is said to be H-free if G contains no induced copies of H. For a class [ABSTRACT FROM AUTHOR]

For a graph G = (V,E), a partition Ω ={O1,O2,...,Ok} of the vertex set V is called a resolving partition if every pair of vertices u,v ∊ V(G) have distinct representations under Ω. The partition dimension of G is the minimum integer k such that G has a resolving k-partition. Many results in determining the partition dimension of graphs have been obtained. However, the known results are limited to connected graphs. In this study, the notion of the partition dimension of a graph is extended so that it can be applied to disconnected graphs as well. Some lower and upper bounds for the partition dimension of a disconnected graph are determined (if they are finite). In this paper, also the partition dimensions for some classes of disconnected graphs are given. [ABSTRACT FROM AUTHOR]

An ordered partition Π of the vertex-set resolves a (not necessarily connected) graph G if the representations of all vertices are distinct. The minimum k such that there is a resolving k -partition Π of G is called the partition dimension of G , and denoted by pd ( G ) or pdd ( G ) for a connected or a disconnected G , respectively. In this paper, we determine the partition dimension of some homogenous disconnected graphs, namely a disjoint union of stars, double stars and some cycles. [ABSTRACT FROM AUTHOR]

We study drawings of graphs on the torus with crossings allowed. A question posed in [M. DeVos, B. Mohar, and R. Šámal, Unexpected behaviour of crossing sequences , J. Combin. Theory Ser. B 101 (2011), no. 6, 448–463], specialized to the case of the torus, asks, whether for every disconnected graph there is a drawing in the torus with the minimal number of crossings, such that one of the graphs is drawn in a planar disc. We reduce the problem to an interesting question from the geometry of numbers and solve a special case. [ABSTRACT FROM AUTHOR]

Abstract: An anticoloring of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. The anticoloring problem seeks, roughly speaking, such colorings with many vertices colored in each color. We deal with the anticoloring problem for planar graphs and, using Lipton and Tarjan’s separation algorithm, provide an algorithm with some bound on the error. We also show that, to solve the anticoloring problem for general graphs, it suffices to solve it for connected graphs. [Copyright &y& Elsevier]

Abstract: We investigate transitive decompositions of disconnected graphs, and show that these behave very differently from a related class of algebraic graph decompositions, known as homogeneous factorisations. We conclude that although the study of homogeneous factorisations admits a natural reduction to those cases where the graph is connected, the study of transitive decompositions does not. [Copyright &y& Elsevier]

Abstract: We consider the problem of reconstructing the characteristic polynomial of a graph from its polynomial deck, i.e. the collection of characteristic polynomials of its vertex-deleted subgraphs. Here we provide a positive answer to this problem for graphs as in the title, provided they are disconnected. Since the same problem for connected graph was already answered in positive, we have arrived at the positive answer for the entire collection of graphs under considerations. [Copyright &y& Elsevier]

Abstract: An anticoloring of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. The anticoloring problem seeks, roughly speaking, for such colorings with many vertices colored in each color. We show that, to solve the anticoloring problem with two colors for general graphs, it suffices to solve it for connected graphs. [Copyright &y& Elsevier]

In 1976 Molluzzo asked for the conditions on a generating string of a Steinhaus graph that would guarantee that its complement would be connected. In this paper we give conditions that guarantee that the complement is not connected and a recursion, for the number of such strings. We also find tight upper and lower bounds for this recursion by examining the recursion dσ(2k) = dσ(k)+dσ(k-1) and dσ(2k+1) = 2dσ(k) + 1. [Copyright &y& Elsevier]

Let G be a simple graph and { 1 , 2 , ... , n } be its vertex set. The polynomial reconstruction problem asks the question: given a deck P (G) containing the n characteristic polynomials of the vertex deleted subgraphs G − 1 , G − 2 , ..., G − n of G, can ϕ (G , x) , the characteristic polynomial of G, be reconstructed uniquely? To date, this long-standing problem has only been solved in the affirmative for some specific classes of graphs. We prove that if there exists a vertex v such that more than half of the eigenvalues of G are shared with those of G − v , then this fact is recognizable from P (G) , which allows the reconstruction of ϕ (G , x) . To accomplish this, we make use of determinants of certain walk matrices of G. Our main result is used, in particular, to prove that the reconstruction of the characteristic polynomial from P (G) is possible for a large subclass of disconnected graphs, strengthening a result by Sciriha and Formosa. [ABSTRACT FROM AUTHOR]

We propose necessary and sufficient conditions for an integer matrix to be decomposable in terms of its Hermite normal form. Specifically, to each integer matrix, we associate a symmetric integer matrix whose reducibility can be efficiently determined by elementary linear algebra techniques, and which completely determines the decomposability of the first one. [ABSTRACT FROM AUTHOR]

We describe and analyze the problems existing on RCR network, a family of scalable interconnection network topologies proposed by Sun and Cheung, which include disconnected graph, the definition of bisection width, and network diameter. And, necessary modifications on some RCA topological parameters including bisection width and network diameter are made. [ABSTRACT FROM AUTHOR]