Domination Defect in Graphs: Guarding With Fewer Guards

In this paper, we introduce a new graph parameter called the domination defect of a graph. The domination number γ of a graph G is the minimum number of vertices required to dominate the vertices of G. Due to the minimality of γ, if a set of vertices of G has cardinality less than γ then there are vertices of G that are not dominated by that set. The k-domination defect of G is the minimum number of vertices which are left un-dominated by a subset of γ - k vertices of G. We study different bounds on the k-domination defect of a graph G with respect to the domination number, order, degree sequence, graph homomorphisms and the existence of efficient dominating sets. We also characterize the graphs whose domination defect is 1 and find exact values of the domination defect for some particular classes of graphs.     

On the intersection graph of a finite group

For a finite group G, the intersection graph of G which is denoted by Γ(G) is an undirected graph such that its vertices are all nontrivial proper subgroups of G and two distinct vertices H and K are adjacent when H ∩ K ≠ 1. In this paper we classify all finite groups whose intersection graphs are regular. Also, we find some results on the intersection graphs of simple groups and finally we study the structure of Aut(Γ(G)).     

Strictly Deza line graphs

For a given graph G, its line graph L(G) is defined as the graph with vertex set equal to the edge set of G in which two vertices are adjacent if and only if the corresponding edges of G have exactly one common vertex. A k-regular graph of diameter 2 on υ vertices is called a strictly Deza graph with parameters (υ, k, b, a) if it is not strongly regular and any two vertices have a or b common neighbors. We give a classification of strictly Deza line graphs.     

Token Graphs

For a graph G and integer k ≥ 1, we define the token graph F _k (G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F _k (G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of F _k (G) correspond to configurations of k indistinguishable tokens placed at distinct vertices of G, where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.     

Graphs of nonsolvable groups with four degree-vertices

Let G be a finite group. The degree(vertex) graph Γ(G) attached to G is a character degree graph.Its vertices are the degrees of the nonlinear irreducible complex characters of G, and different vertices m, n are adjacent if the greatest common divisor(m, n) 1. In this paper, we classify all graphs with four vertices that occur as Γ(G) for nonsolvable groups G.     

Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

Proper connection number of bipartite graphs

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

Recognition of characteristically simple group <Emphasis Type="Italic">A</Emphasis><Subscript>5</Subscript> × <Emphasis Type="Italic">A</Emphasis><Subscript>5</Subscript> by character degree graph and order

The character degree graph of a finite group G is the graph whose vertices are the prime divisors of the irreducible character degrees of G and two vertices p and q are joined by an edge if pq divides some irreducible character degree of G. It is proved that some simple groups are uniquely determined by their orders and their character degree graphs. But since the character degree graphs of the characteristically simple groups are complete, there are very narrow class of characteristically simple groups which are characterizable by this method.We prove that the characteristically simple group A₅ × A₅ is uniquely determined by its order and its character degree graph. We note that this is the first example of a non simple group which is determined by order and character degree graph. As a consequence of our result we conclude that A₅ × A₅ is uniquely determined by its complex group algebra.     

On one test for the switching separability of graphs modulo <Emphasis Type="Italic">q</Emphasis>

We consider graphs whose edges are marked by numbers (weights) from 1 to q - 1 (with zero corresponding to the absence of an edge). A graph is additive if its vertices can be marked so that, for every two nonadjacent vertices, the sum of the marks modulo q is zero, and for adjacent vertices, it equals the weight of the corresponding edge. A switching of a given graph is its sum modulo q with some additive graph on the same set of vertices. A graph on n vertices is switching separable if some of its switchings has no connected components of size greater than n - 2. We consider the following separability test: If removing any vertex from G leads to a switching separable graph then G is switching separable. We prove this test for q odd and characterize the set of exclusions for q even. Connection is established between the switching separability of a graph and the reducibility of the n-ary quasigroup constructed from the graph.     

Group distance magic and antimagic graphs

Given a graph G with n vertices and an Abelian group A of order n, an A-distance antimagic labelling of G is a bijection from V (G) to A such that the vertices of G have pairwise distinct weights, where the weight of a vertex is the sum (under the operation of A) of the labels assigned to its neighbours. An A-distance magic labelling of G is a bijection from V (G) to A such that the weights of all vertices of G are equal to the same element of A. In this paper we study these new labellings under a general setting with a focus on product graphs. We prove among other things several general results on group antimagic or magic labellings for Cartesian, direct and strong products of graphs. As applications we obtain several families of graphs admitting group distance antimagic or magic labellings with respect to elementary Abelian groups, cyclic groups or direct products of such groups.     

Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition \(E_1 \cup E_2 \cup \cdots \cup E_k\) of the edge set E(G) such that each \(E_i\) induces a locally irregular graph. It was recently conjectured by Baudon et al. that every undirected graph admits a decomposition into at most three locally irregular graphs, except for a well-characterized set of indecomposable graphs. We herein consider an oriented version of this conjecture. Namely, can every oriented graph be decomposed into at most three locally irregular oriented graphs, i.e. whose adjacent vertices have distinct outdegrees? We start by supporting this conjecture by verifying it for several classes of oriented graphs. We then prove a weaker version of this conjecture. Namely, we prove that every oriented graph can be decomposed into at most six locally irregular oriented graphs. We finally prove that even if our conjecture were true, it would remain NP-complete to decide whether an oriented graph is decomposable into at most two locally irregular oriented graphs.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

On the diameter of the intersection graph of a finite simple group

Let G be a finite group. The intersection graph Δ_G of G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of G, and two distinct vertices X and Y are adjacent if X ∩ Y ≠ 1, where 1 denotes the trivial subgroup of order 1. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters of intersection graphs of finite non-abelian simple groups have an upper bound 28. In particular, the intersection graph of a finite non-abelian simple group is connected.     

Building Graphs Whose Independence Polynomials Have Only Real Roots

A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is

$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$

where s _k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).

Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic).     

Unicyclic nonintegral sum graphs

A graph G = (V,E) is an integral sum graph if there exists a labeling S(G) ? Z such that V = S(G) and every two distinct vertices u, υ ∈ V are adjacent if and only if u + υ ∈ V. A connected graph G = (V,E) is called unicyclic if |V| = |E|. In this paper two infinite series are constructed of unicyclic graphs that are not integral sum graphs.     

Atomic subspaces of {L_1}-martingale spaces

In Part I of the present paper the following problem was investigated. Let G be a finite simple graph, and S be a finite set of primes. We say that G is representable with S if it is possible to attach rational numbers to the vertices of G such that the vertices v₁, v₂ are connected by an edge if and only if the difference of the attached values is an S-unit. In Part I we gave several results concerning the representability of graphs in the above sense.     

<Emphasis Type="Italic">r</Emphasis>-Dynamic Chromatic Number of Some Line Graphs

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, deg(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the smallest k such that G admits an r-dynamic coloring with k colors. In this paper, we obtain the r-dynamic chromatic number of the line graph of helm graphs H_n for all r between minimum and maximum degree of H_n. Moreover, our proofs are constructive, what means that we give also polynomial time algorithms for the appropriate coloring. Finally, as the first, we define an equivalent model for edge coloring.     

Neighborhood contraction in graphs

Let G be a graph and v be any vertex of G. Then the neighborhood contracted graphG_v of G, with respect to the vertex v, is the graph with vertex set V ? N(v), where two vertices u,w ∈ V ? N(v) are adjacent in G_v if either w = v and u is adjacent to any vertex of N(v) in G or u,w ? N[v] and u,w are adjacent in G. The properties of the neighborhood contracted graphs are discussed in this paper. The neighborhood contraction in some special class of graphs, the domination in a graph and the neighborhood contracted graphs are discussed in the paper.     

The Four-in-a-Tree Problem in Triangle-Free Graphs

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n ⁴) whether three given vertices of a graph belong to an induced tree. Here, we study four-in- a-tree for triangle-free graphs. We give a structural answer to the following question: what does a triangle-free graph look like if no induced tree covers four given vertices? Our main result says that any such graph must have the “same structure”, in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.