Star saturation number of random graphs

For a given graph $F$, the $F$-saturation number of a graph $G$ is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. Recently, the $F$-saturation number of the Erd?s–Rényi random graph $\mathbb{G}(n,p)$ has been determined asymptotically for any complete graph $F$. In this paper, we give an asymptotic formula for the $F$-saturation number of $\mathbb{G}(n,p)$ when $F$ is a star graph.     

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs

We prove that, for a certain positive constant a and for an infinite set of values of n, the number of nonisomorphic triangular embeddings of the complete graph K_n is at least n^an2. A similar lower bound is also given, for an infinite set of values of n, on the number of nonisomorphic triangular embeddings of the complete regular tripartite graph K_n,n,n.     

A sharp upper bound on the spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. The eigenvalues of a graph are the eigenvalues of its adjacency matrix. We obtain an upper bound on the spectral radius of the adjacency matrix and characterize graphs for which the bound is attained.     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

A better bound for the cop number of general graphs

In this note, we prove that the cop number of any n‐vertex graph G, denoted by , is at most . Meyniel conjectured . It appears that the best previously known sublinear upper‐bound is due to Frankl, who proved . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008     

A lower bound for the convexity number of some graphs

Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1.     

Extremal perfect graphs for a bound on the domination number

We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+β_v(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and β_v(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.     

Dominating sets and domatic number of circular arc graphs

A dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets. The problems of finding a minimum cardinality dominating set and the domatic number are both NP-complete even for special classes of graphs. In the present paper we give an O(n∣E∣) time algorithm that finds a minimum cardinality dominating set when G is a circular arc graph (intersection graph of arcs on a circle). The domatic number problem is solved in O(n² log n) time when G is a proper circular arc graph, and it is shown NP-complete for general circular arc graphs.     

A lower bound on the number of sharp shadow-boundaries of convex polytopes

We give the lower bound on the number of sharp shadow-boundaries of convexd-polytopes (or unbounded convex polytopal sets) withn facets. The polytopes (sets) attaining these bounds are characterized. Additionally, our results will be transferred to the dual theory.The research work of the first author was (partially) supported by Hungarian National Foundation for Scientific Research, grant no. 1812.     

The lower bound on independence number

Let G be a graph with degree sequence ( d_v). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least , where f_m+1( x) is a function greater than for x> 0. For a weighted graph G = ( V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least where w_v is the weight of v.     

A tight bound on the number of mobile servers to guarantee transferability among dominating configurations

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of nodes, and assume that a user can receive the service if at least one adjacent node (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees consisting of n nodes, ⌊n/2⌋ mobile servers are sometimes necessary and always sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with n nodes, ⌈(n+1)/3⌉ mobile servers are sometimes necessary and always sufficient.     

Parameters for which the Griesmer bound is not sharp

We prove for a large class of parameters t and r that a multiset of at most tθ_d-k+rθ_d-k-2 points in PG(d,q) that blocks every k-dimensional subspace at least t times must contain a sum of t subspaces of codimension k.We use our results to identify a class of parameters for linear codes for which the Griesmer bound is not sharp. Our theorem generalizes the non-existence results from Maruta [On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12 (1997) 83-87] and Klein [On codes meeting the Griesmer bound, Discrete Math. 274 (2004) 289-297].     

一类连通无三角形图线图的共色数的下界

Erd(o)s,Gimbel and Straight (1990) conjectured that if ω(G)＜5 and z(G)＞3,then z(G)≥χ(G)-2. But by using the concept of edge cochromatic number it is proved that if G is the line graph of a connected triangle-free graph with ω(G)＜5 and G≠K4, then z(G)≥χ(G)-2.     

Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.     

Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n² log⁵ n) time and O(n²) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs.     

Lower bounds for the domination number and the total domination number of direct product graphs

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γ_t(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.