Search

Let $$k\ge 2$$ be an integer. A $$P_{\ge k}$$ -factor of a graph G is its spanning subgraph each of whose components is a path of order at least k. A graph G is $$P_{\ge k}$$ -factor covered if for any edge e of G, G has a $$P_{\ge k}$$ -factor containing e. A graph G is $$P_{\ge k}$$ -factor deleted if for any edge e of G, G has a $$P_{\ge k}$$ -factor excluding e. A graph G is $$(P_{\ge k},n)$$ -factor critical covered if for any $$Q\subseteq V(G)$$ with $$|Q|=n$$ , the graph $$G-Q$$ is $$P_{\ge k}$$ -factor covered. A graph G is $$(P_{\ge k},n)$$ -factor critical deleted if for any $$Q\subseteq V(G)$$ with $$|Q|=n$$ , the graph $$G-Q$$ is $$P_{\ge k}$$ -factor deleted. Zhou et al. (Contribut Dis Math 14(1): 167–174, 2019) introduced the sun toughness of a graph G, which is denoted by s(G) and defined by $$\begin{aligned} s(G)=\min \left\{ \frac{|X|}{sun(G-X)}:X\subseteq V(G),sun(G-X)\ge 2\right\} \end{aligned}$$ if G is not a complete graph; otherwise, $$s(G)=+\infty $$ . In this article, we prove that (i) an $$(n+r+2)$$ -connected graph G is $$(P_{\ge 3},n)$$ -factor critical deleted if $$s(G)>\frac{n+r+3}{2(r+2)}$$ , where $$n\ge 0$$ and $$r\ge 0$$ are two integers; (ii) an $$(n+r+1)$$ -connected graph G is $$(P_{\ge 3},n)$$ -factor critical covered if $$s(G)>\frac{n+r+1}{2r+1}$$ , where $$n\ge 0$$ and $$r\ge 1$$ are two integers.

A spanning subgraph of a graph G is called a path-factor of G if its each component is a path. A path-factor is called a 𝒫≥k-factor of G if its each component admits at least k vertices, where k ≥ 2. (Zhang and Zhou, Discrete Math. 309 (2009) 2067–2076) defined the concept of 𝒫≥k-factor covered graphs, i.e., G is called a 𝒫≥k-factor covered graph if it has a 𝒫≥k-factor covering e for any e∈ E(G). In this paper, we firstly obtain a minimum degree condition for a planar graph being a 𝒫≥2-factor and 𝒫≥3-factor covered graph, respectively. Secondly, we investigate the relationship between the maximum degree of any pairs of non-adjacent vertices and 𝒫≥k-factor covered graphs, and obtain a sufficient condition for the existence of 𝒫≥2-factor and 𝒫≥3-factor covered graphs, respectively.

For two integers $$k>0$$ k > 0 and $$\ell $$ ℓ , a graph $$G=(V,E)$$ G = ( V , E ) is called $$(k,\ell )$$ ( k , ℓ ) -tight if $$|E|=k|V|-\ell $$ | E | = k | V | - ℓ and $$i_G(X)\le k|X|-\ell $$ i G ( X ) ≤ k | X | - ℓ for each $$X\subseteq V$$ X ⊆ V for which $$i_G(X)\ge 1$$ i G ( X ) ≥ 1 , where $$i_G(X)$$ i G ( X ) denotes the number of induced edges by X. G is called $$(k,\ell )$$ ( k , ℓ ) -redundant if $$G-e$$ G - e has a spanning $$(k,\ell )$$ ( k , ℓ ) -tight subgraph for all $$e\in E$$ e ∈ E . We consider the following augmentation problem. Given a graph $$G=(V,E)$$ G = ( V , E ) that has a $$(k,\ell )$$ ( k , ℓ ) -tight spanning subgraph, find a graph $$H=(V,F)$$ H = ( V , F ) with the minimum number of edges, such that $$G\cup H$$ G ∪ H is $$(k,\ell )$$ ( k , ℓ ) -redundant. We give a polynomial algorithm and a min-max theorem for this augmentation problem when the input is $$(k,\ell )$$ ( k , ℓ ) -tight. For general inputs, we give a polynomial algorithm when $$k\ge \ell $$ k ≥ ℓ and show the NP-hardness of the problem when $$k k < ℓ . Since $$(k,\ell )$$ ( k , ℓ ) -tight graphs play an important role in rigidity theory, these algorithms can be used to make several types of rigid frameworks redundantly rigid by adding a smallest set of new bars.

We present two extremal results on 4-cycles. Let q be a large even integer. First we prove that every ( q 2 + q + 1 ) -vertex C 4 -free graph with more than 1 2 q ( q + 1 ) 2 − 0.2 q edges must be a spanning subgraph of a unique polarity graph. This implies a stability refinement of a special case of the seminal work of Furedi on the extremal number of C 4 . Second we prove that every ( q 2 + q + 1 ) -vertex graph with 1 2 q ( q + 1 ) 2 + 1 edges contains at least q − 1 copies of C 4 , where we also characterize the extremal graphs. This confirms infinitely many cases of a longstanding conjecture of Erdős and Simonovits on the number of C 4 . The proof of the first result combines some earlier and novel ideas, while the proof of the second result builds on the first stability result.

A P≥k-factor of a graph G is a spanning subgraph of G whose components are paths of order at least k. We say that a graph G is P≥k-factor covered if for every edge e ∈ E(G), G admits a P≥k-factor that contains e; and we say that a graph G is P≥k-factor uniform if for every edge e ∈ E(G), the graph G−e is P≥k-factor covered. In other words, G is P≥k-factor uniform if for every pair of edges e1, e2 ∈ E(G), G admits a P≥k-factor that contains e1 and avoids e2. In this article, we testify that (1) a 3-edge-connected graph G is P≥k-factor uniform if its isolated toughness I(G) > 1; (2) a 3-edge-connected graph G is P≥k-factor uniform if its isolated toughness I(G) > 2. Furthermore, we explain that these conditions on isolated toughness and edge-connectivity in our main results are best possible in some sense.

There are several approaches to lower the complexity of huge networks. One of the key notions is that of twin nodes, exhibiting the same connection pattern to the rest of the network. We extend this idea by defining a twin preserving spanning subgraph (TPS-subgraph) of a simple graph as a tool to compute certain graph related invariants which are preserved by the subgraph. We discuss how these subgraphs preserve some distance based parameters of the simple graph. We introduce a sub-skeleton graph on a vector space and examine its basic properties. The sub-skeleton graph is a TPS-subgraph of the non-zero component graph defined over a vector space. We prove that some parameters like the metric-dimension are preserved by the sub-skeleton graph.

Given a metric graph G = ( V , E , w ) and an integer k, we aim to find a single allocation k-hub location, which is a spanning subgraph consisting of a clique of size k such that every node outside of the clique is adjacent to exactly one node inside the clique. For various objective functions studied in the literature, we present improved hardness and approximation results.

Let $ G $ be a graph. For a set $ \mathcal{H} $ of connected graphs, an $ \mathcal{H} $-factor of a graph $ G $ is a spanning subgraph $ H $ of $ G $ such that every component of $ H $ is isomorphic to a member of $ \mathcal{H} $. A graph $ G $ is called an $ (\mathcal{H}, m) $-factor deleted graph if for every $ E'\subseteq E(G) $ with $ |E'| = m $, $ G-E' $ admits an $ \mathcal{H} $-factor. A graph $ G $ is called an $ (\mathcal{H}, n) $-factor critical graph if for every $ N\subseteq V(G) $ with $ |N| = n $, $ G-N $ admits an $ \mathcal{H} $-factor. Let $ m $, $ n $ and $ k $ be three nonnegative integers with $ k\geq2 $, and write $ \mathcal{F} = \{P_2, C_3, P_5, \mathcal{T}(3)\} $ and $ \mathcal{H} = \{K_{1, 1}, K_{1, 2}, \cdots, K_{1, k}, \mathcal{T}(2k+1)\} $, where $ \mathcal{T}(3) $ and $ \mathcal{T}(2k+1) $ are two special families of trees. In this article, we verify that (i) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{F}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{4m+2}{2m+3} $; (ii) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{F}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{3} $; (iii) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{H}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{2}{2k-1} $; (iv) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{H}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{2k+1} $.

Given a graph G and an integer $$k\ge 2$$ . A spanning subgraph F of a graph G is said to be a $$P_{\ge k}$$ -factor of G if each component of F is a path of order at least k. A graph G is called a $$P_{\ge k}$$ -factor uniform graph if for any two distinct edges $$e_{1}$$ and $$e_{2}$$ of G, G admits a $$P_{\ge k}$$ -factor including $$e_{1}$$ and excluding $$e_{2}$$ . More recently, Zhou and Sun (Discret Math 343:111715, 2020) gave binding number conditions for a graph to be $$P_{\ge 2}$$ -factor and $$P_{\ge 3}$$ -factor uniform graphs, respectively. In this paper, we present toughness and isolated toughness conditions for a graph to be a $$P_{\ge 3}$$ -factor uniform graph, respectively.

A spanning subgraph of a graph is defined as a path factor of the graph if its component are paths. A P≥n-factor means a path factor with each component having at least n vertices. A graph G is defined as a (P≥n, m)-factor deleted graph if G–E′ has a P≥n-factor for every E′ ⊆ E(G) with |E′| = m. A graph G is defined as a (P≥n, k)-factor critical graph if after deleting any k vertices of G the remaining graph of G admits a P≥n-factor. In this paper, we demonstrate that (i) a graph G is (P≥3, m)-factor deleted if κ(G) ≥ 2m + 1 and bind(G) ≥ 2/3 - $ \frac{3}{2}-\frac{1}{4m+4}$; (ii) a graph G is (P≥3, k)-factor critical if κ(G) ≥ k + 2 and bind(G) ≥ $ \frac{5+k}{4}$.

It is well known that if $$G = (V, E)$$ G = ( V , E ) is a connected multigraph and $$X\subset V$$ X ⊂ V is a subset of even order, then G contains a spanning forest H such that each vertex from X has an odd degree in H and all the other vertices have an even degree in H. This spanning forest may have isolated vertices. If this is not allowed in H, then the situation is much more complicated. In this paper, we study this problem and generalize the concepts of even-factors and odd-factors in a unified form.

A spanning subgraph H of a graph G is a $$P_{3}$$ -factor of G if every component of H is a path of order three. The square of a graph G, denoted by $$G^{2}$$ , is the graph with vertex set V(G) such that two vertices are adjacent in $$G^{2}$$ if and only if their distance in G is at most 2. A graph G is subcubic if it has maximum degree at most three. In this paper, we give a sharp necessary condition for the existence of $$P_{3}$$ -factors in the square of a tree, which improves a result of Li and Zhang (Graphs Combin 24:107–111, 2008). In addition, we will also present a sufficient condition for the existence of $$P_{3}$$ -factors in the square of a tree, which has the following interesting application to subcubic trees: if T is a subcubic tree of order 3n such that $$|L(T-L(T))|\le 7$$ , then $$T^{2}$$ has a $$P_{3}$$ -factor, where L(T) denotes the set of leaves in T. Examples show that the upper bound 7 on $$|L(T-L(T))|$$ is sharp.

A path factor of G is a spanning subgraph of G such that its each component is a path. A path factor is called a P≥n-factor if its each component admits at least n vertices. A graph G is called P≥n-factor covered if G admits a P≥n-factor containing e for any e ∈ E(G), which is defined by [Discrete Mathematics, 309, 2067–2076 (2009)]. We first define the concept of a (P≥n, k)-factor-critical covered graph, namely, a graph G is called (P≥n, k)-factor-critical covered if G-D is P≥n-factor covered for any D ⊆ V(G)with ∣D∣ = k. In this paper, we verify that (i) a graph G with k(G) ≥ k + 1 is (P⊆2, k)-factor-critical covered if bind $$\left( G \right) > {{2 + k} \over 3}$$ ; (ii) a graph G with ∣V(G)∣ ≥ k + 3 and k(G) ≥ k + 1 is (P≥3, k)-factor-critical covered if bind $$\left( G \right) \ge {{4 + k} \over 3}$$ .

Bollobás and Scott conjectured that every graph G has a balanced bipartite spanning subgraph H such that for each for each In this paper, we consider the contrary side and show that every graphic sequence has a realization G which admits a balanced bipartite spanning subgraph H such that for each and we show that the bound is sharp.

A locating-dominating set of a graph G is a dominating set of G such that every vertex of G outside the dominating set is uniquely identified by its neighborhood within the dominating set. The location-domination number of G is the minimum cardinality of a locating-dominating set in G. Let G 1 and G 2 be two disjoint copies of a graph G and f : V ( G 1 ) → V ( G 2 ) be a function. A functigraph F G f consists of vertex set V ( G 1 ) ∪ V ( G 2 ) and edge set E ( G 1 ) ∪ E ( G 2 ) ∪ { u v : v = f ( u ) } . In this paper, we study the variation of location-domination number in passing from G to F G f and find its sharp lower and upper bounds. We also study location-domination number of functigraphs of complete graphs for all possible definitions of function f. We also obtain location-domination number of functigraphs of a family of spanning subgraph of the complete graphs.

A t -bar visibility representation of a graph G assigns each vertex up to t horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of positive width. The least t such that G has a t -bar visibility representation is the bar visibility number of G , denoted by b ( G ) . We show that if H is a spanning subgraph of G , then b ( H ) ≤ b ( G ) + 1 . It follows that b ( G ) ≤ ⌈ n ∕ 6 ⌉ + 1 when G is an n -vertex graph. This improves the upper bound obtained by Chang et al. (2004).

Bollobas and Scott [5] conjectured that every graph G has a balanced bipartite spanning subgraph H such that for each v ∈ V ( G ) , d H ( v ) ≥ ( d G ( v ) − 1 ) / 2 . In this paper, we show that every graphic sequence has a realization for which this Bollobas-Scott conjecture holds, confirming a conjecture of Hartke and Seacrest [8] . On the other hand, we give an infinite family of counterexamples to this Bollobas-Scott conjecture, which indicates that ⌊ ( d G ( v ) − 1 ) / 2 ⌋ (rather than ( d G ( v ) − 1 ) / 2 ) is probably the correct lower bound. We also study bipartitions V 1 , V 2 of graphs with a fixed number of edges. We provide a (best possible) upper bound on e ( V 1 ) λ + e ( V 2 ) λ for any real λ ≥ 1 (the case λ = 2 is a question of Scott [12] ) and answer a question of Scott (Problem 3.9 in [12] ) on max ⁡ { e ( V 1 ) , e ( V 2 ) } .

A path cover of a graph G is a spanning subgraph of G consisting of vertex disjoint paths; a minimum path cover of G is a path cover of G consisting of minimum number of paths; a path cover number of G, denoted by p(G), is the number of paths in a minimum path cover of G, i.e., $$p(G)=\min \{|{\mathcal {P}}|:$$$${\mathcal {P}}$$ is a path cover of $$G\}.$$ A graph G is quasi-claw-free if for any two vertices x, y with $$d(x,y)=2$$ in G, there exists a vertex u with $$u\in N(x)\cap N(y)$$ and $$N(u)\subseteq N[x]\cup N[y].$$ In this paper, we prove that for any quasi-claw-free graph G of order n, if $$\sigma _{k+1}(G)\ge {n-k}$$ for a positive integer k, then $$p(G)\le k,$$ where $$\sigma _{k+1}(G)$$ is the minimum degree sum of an independent set with $$k+1$$ vertices in G. Our result is a generalization of Ore’s sufficient conditions of hamiltonicity for quasi-claw-free graphs.

Given graphs G and H, a family of vertex-disjoint copies of H in G is called an H-tiling. Conlon, Gowers, Samotij and Schacht showed that for a given graph H and a constant γ>0, there exists C>0 such that if $p \ge C{n^{ - 1/{m_2}(H)}}$ , then asymptotically almost surely every spanning subgraph G of the random graph 𝒢(n, p) with minimum degree at least $\delta (G) \ge (1 - \frac{1}{{{\chi _{{\rm{cr}}}}(H)}} + \gamma )np$ contains an H-tiling that covers all but at most γn vertices. Here, χcr(H) denotes the critical chromatic number, a parameter introduced by Komlós, and m2(H) is the 2-density of H. We show that this theorem can be bootstrapped to obtain an H-tiling covering all but at most $\gamma {(C/p)^{{m_2}(H)}}$ vertices, which is strictly smaller when $p \ge C{n^{ - 1/{m_2}(H)}}$ . In the case where H = K3, this answers the question of Balogh, Lee and Samotij. Furthermore, for an arbitrary graph H we give an upper bound on p for which some leftover is unavoidable and a bound on the size of a largest H -tiling for p below this value.

For a set ℋ of connected graphs, a spanning subgraph H of a graph G is called an ℋ-factor of G if every component of H is isomorphic to a member ofℋ. An H-factor is also referred as a component factor. If each component of H is a star (resp. path), H is called a star (resp. path) factor. By a P≥ k-factor (k positive integer) we mean a path factor in which each component path has at least k vertices (i.e. it has length at least k − 1). A graph G is called a P≥ k-factor covered graph, if for each edge e of G, there is a P≥ k-factor covering e. In this paper, we prove that (1) a graph G has a {K1,1,K1,2, … ,K1,k}-factor if and only if bind(G) ≥ 1/k, where k ≥ 2 is an integer; (2) a connected graph G is a P≥ 2-factor covered graph if bind(G) > 2/3; (3) a connected graph G is a P≥ 3-factor covered graph if bind(G) ≥ 3/2. Furthermore, it is shown that the results in this paper are best possible in some sense.

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.

A Hamiltonian cycle in a graph is a spanning subgraph that is homeomorphic to a circle. With this in mind, it is natural to define a Hamiltonian d-sphere in a d-dimensional simplicial complex as a spanning subcomplex that is homeomorphic to a d-dimensional sphere. We consider the Linial-Meshulam model for random simplicial complexes, and prove that there is a sharp threshold at $p=\sqrt{\frac{e}{\gamma n}}$ for the appearance of a Hamiltonian $2$-sphere in a random $2$-complex, where $\gamma = 4^4/3^3$., Comment: Main changes from last version: An explanation of the proof structure was added as a subsection in the introduction. A computational mistake in Lemma 4.5 was corrected, and a result some constants throughout the proof had to be modified (in the definition of good graph, in the final estimation) . Some other minor corrections

In this paper, a containment control issue for discrete-time second-order multi-agents (MASs) with asynchronous intermittent communication is analyzed, where each agent communicates with some of its neighbors at certain discrete time according to its own clock rather than the complete discrete process and all agents’ clocks are independent of each other. By constructing the spanning subgraph of communication topology at each discrete time, the stability analysis of containment control under the asynchronous intermittent communication is equivalently transformed into the products convergence of nonnegative matrices. Hybrid tools including matrix theory and the composite binary relation are utilized to analyze this convergence issue. Unlike the existing results on the containment control with fixed topology, in which the followers will gradually enter into the convex hull constructed by the leaders and their final positions are fixed, it is theoretically proved in this paper that although the followers will enter into the convex hull of the leaders under the asynchronous intermittent communication, their positions after entering the convex hull may always be time-varying. Finally, the theoretical finding is verified by a simulation example.

The Cartesian product of n cycles is a 2n-regular, 2n-connected and bi- pancyclic graph. Let G be the Cartesian product of n even cycles and let 2n = n1+ n2+ ・ ・ ・ + nkwith k ≥ 2 and ni≥ 2 for each i. We prove that if k = 2, then G can be decomposed into two spanning subgraphs G1and G2such that each Giis ni-regular, ni-connected, and bipancyclic or nearly bipancyclic. For k > 2, we establish that if all niin the partition of 2n are even, then G can be decomposed into k spanning subgraphs G1,G2, . . . ,Gk such that each Giis ni-regular and ni-connected. These results are analo- gous to the corresponding results for hypercubes.

We show that the square of every connected S ( K 1 , 4 ) -free graph satisfying a matching condition has a 2-connected spanning subgraph of maximum degree at most 3. Furthermore, we characterise trees whose square has a 2-connected spanning subgraph of maximum degree at most k. This generalises the results on S ( K 1 , 3 ) -free graphs of Henry and Vogler [7] and Harary and Schwenk [6] , respectively.